5.2: Funktion der Hilfsgraphen?

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

5.2: Funktion der Hilfsgraphen?

Beitrag von headhumper »

Hallo,

ich verstehe leider überhaupt nicht, was mir die angegebenen Graphen sagen sollen.
Ich würde meine Frage gerne spezifischer stellen, aber es scheint mir der grundsätzliche Zugang zu fehlen.

Also, wie sind die Graphen G_h und G_or zu verstehen? Wie funktionieren sie? Wie erfüllen sie die auf dem Blatt angegebenen Eigenschaften?

Gruß

Alby407
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 19. Jul 2014 15:40

Re: 5.2: Funktion der Hilfsgraphen?

Beitrag von Alby407 »

Ich verstehe sie auch nicht so ganz.
Den or-Graphen zu erweitern wird kein Problem sein, denke ich (einfach einen dritten Knoten als drittes Literal und einen leeren Knoten hinzufügen?).

Beim h-Graphen verstehe ich nicht ganz, was die 0,1 und 2 Knoten darstellen sollen. Zumal von den Eingangsknoten nur eine Verbindung zu Knoten 2 besteht. Also muss 2 irgendeine Reaktion auf 0 und 1 haben.

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: 5.2: Funktion der Hilfsgraphen?

Beitrag von headhumper »

Ich glaube ich bin etwas weiter :idea:

G_h: Damit 3-COL erfüllt ist, müssen x und ~x die Werte 0 bzw. 1 haben, da alle x_n und ~x_n mit der 2 verbunden sind. Damit bleiben für die anderen Knoten ja nur noch 0 und 1 übrig, und entweder muss x_n = 1 und ~x_n = 0 sein oder umgekehrt (da diese nicht nur mit der 2 sondern auch untereinander verbunden sind). Damit ist 3-COL erfüllt (jeder Nachbar hat eine andere Farbe [0, 1, 2]) und die x_n sind entweder "wahr" (1) oder "falsch" (0)

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: 5.2: Funktion der Hilfsgraphen?

Beitrag von R_Egert »

Hallo zusammen,

Die generelle Funktionalität der beiden Hilfsgraphen sind auf dem Übungsblatt unter dem Punkt Hinweise beschrieben... Aber vll etwas anders formuliert:

Vorweg: 0,1,2 sind in unserem Fall die 3 Farben für das 3-Col Problem (Alternativ können Sie farben Ihrer wahl benutzen, aber da wir versuchen eine boolsche Logik zu reduzieren bietet sich 0,1 und 2 an ;)).

G_or: Der Ausgangsknoten soll genau dann mit einer 1 gefärbt werden können wenn eine deratrige Belegung von Literalen anliegt, sodass das logische ODER dieser Literale "wahr" ergeben würde.

G_h: Wofür sorgt denn ein Hilfsgraph bei dem jedes Literal mit seinem Komplement und und alle Literale (und Komplemente) mit der 2 Verbunden werden. Halten Sie sich bei der beantwortung dieser Frage die Regeln für die 3-färbbarkeit von Graphen im Hinterkopf.

Ich hoffe das hilft vielleicht etwas weiter?

Viele Grüße,

Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: 5.2: Funktion der Hilfsgraphen?

Beitrag von headhumper »

Ich habe das Thema jetzt im Buch "Computational complexity: a conceptual perspective" nachgeschlagen, dort ist es (Reduktion 3CNF auf 3COL) hervorragend erklärt. Ich verstehe die Hinweise jetzt, nachdem ich es dort nachgelesen habe :oops:

(Ich war sehr verwirrt davon, ein logisches ODER auf "Farben" anzuwenden, aber der Trick ist natürlich eine Farbe mit "wahr" und eine Farbe mit "falsch" zu identifizieren. Der Schritt ist natürlich trivial, aber ich habe mich wohl zu sehr an den Begriff "Farbe" geklammert.)

Benutzeravatar
Centaur
Erstie
Erstie
Beiträge: 18
Registriert: 27. Apr 2015 10:51

Re: 5.2: Funktion der Hilfsgraphen?

Beitrag von Centaur »

R_Egert hat geschrieben: ...
G_or: Der Ausgangsknoten soll genau dann mit einer 1 gefärbt werden können wenn eine deratrige Belegung von Literalen anliegt, sodass das logische ODER dieser Literale "wahr" ergeben würde.
...
Genau dabei liegt momentan unser Problem, was ist die 'logische or Funktion' bei Farben?
Soll das heißen, dass (x1 == 1 || x2 == 1) gelten muss?

Viele Grüße und dane für die Hilfe hier, beim letzten Testat echt nötig :)
One may feel fear in the face of danger so long as one banishes fear when danger actually arrives

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: 5.2: Funktion der Hilfsgraphen?

Beitrag von headhumper »

Centaur hat geschrieben:Genau dabei liegt momentan unser Problem, was ist die 'logische or Funktion' bei Farben?
Lies mal den Post vor deinem :shock:

Antworten

Zurück zu „Archiv“