Theorie 5 Aufgabe 2

MikMik
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 24. Apr 2015 18:56

Theorie 5 Aufgabe 2

Beitrag von MikMik »

Ich habe eine Frage zu der 2. Aufgabe und zwar habe ich diese jetzt soweit bearbeitet, dass ich die beiden Oder mit drei Eingängen mit einer Verwundung verbunden habe und somit eine Graphen habe, mit welchem ich der gegebenen Formel entsprechen kann, leider unterscheidet dieser noch nicht zwischen Färbbarkeit und nicht Färbbarkeit und ich weiß nicht wie ich diese Problem in den Griff bekommen kann.
Zwar habe ich schon versucht durch noch extra Kanten bestimmte Belegungen zu Verhindern und den Graphen so in den gewünschten Fällen nicht färbar zu machen, aber trotz mehren Stunden des Versuches bin ich nicht wirklich weiter gekommen.
Was kann ich an dieser Stelle tun? Gibt es irgendeinen Trick welcher mir nicht bekannt ist oder ist mein Lösungsansatz gänzlich falsch?

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

Re: Theorie 5 Aufgabe 2

Beitrag von R_Egert »

Was meinst du mit "Verwundung"?

Klingt ansonsten jedenfalls so als würde das in die richtige Richtung gehen. Nachdem man das "Or" erweitert hat, muss man sich überlegen wie man das mit dem gegeben Hilfsgraphen derart zu einem Graphen vereinigt, dass dieser genau dann 3-färbbar ist, wenn eine gültige Belegung vorliegt. Dazu muss man sich halt nun überlegen was bei den "Or" passieren muss wenn eine ungültige Belegung anliegt. Dein Gedankengang geht in die richtige Richtung.

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

AlexIschuk
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 11. Apr 2015 10:22

Re: Theorie 5 Aufgabe 2

Beitrag von AlexIschuk »

Muss der Gor Graph auch 3-Col sein? Er ist es ja offensichtlich mit 2 Eingangsvariablen. Soll Gor diese Eigenschaft nach der Erweiterung beibehalten? Bei mir hat Gor nach der Erweiterung eine 4-Faerbarkeit.

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

Re: Theorie 5 Aufgabe 2

Beitrag von R_Egert »

Hallo ja die 3-färbbarkeit muss beibehalten werden, da ja ansonsten nicht auf das 3-col Problem reduziert wird.

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

Smith
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 13. Apr 2015 15:45

Re: Theorie 5 Aufgabe 2

Beitrag von Smith »

AlexIschuk hat geschrieben:Muss der Gor Graph auch 3-Col sein? Er ist es ja offensichtlich mit 2 Eingangsvariablen.
Die Offensichtlichkeit erschließt sich mir leider nicht... allerdings bin ich auch wohl noch nicht so weit in der Aufgabe durchgedrungen wie du.
Kannst du erklären wie du diese Eigenschaft aus dem Graphen abliest?

Ich verstehe wohl auch noch nicht ganz was die 2 leeren Felder sollen...

Ich dachte der Ausgang bekommt entweder ein Ja (logisches ODER ergibt 1, also x1 = 1 und x2 = 0 oder x1 = 0 und x2 = 1 oder x1 = 1 und x2 = 1) oder ein Nein (Belegung 0 - 0).
Wie kommt dabei eine 3-färbbarkeit zustande?
Phil

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

Re: Theorie 5 Aufgabe 2

Beitrag von R_Egert »

Anwendung der 3-Col Definition: Ein Graph ist genau dann 3-färbbar, wenn man allen Knoten eine Farbe zuweisen kann und zwar derart, dass keine zwei miteinander verbundenen Knoten die gleiche Farbe erhalten.

Für den G_or Graphen würde z.b. bei der Färbung 0,0 für die beiden Eingangsliterale für die beiden darüberliegenden Knoten jeweils die Farben 1 und 2 übrig bleiben. Diese beiden Knoten wiederum müssen unterschiedlich gefärbt werden, da sie ebenfalls miteinander verbunden sind. Färbt man diese nun mit 1,2 dann bleibt für den Ausgangsknoten nurnoch die Farbe 0, da dieser wiederum mit den beiden Knoten (1 und 2) verbunden ist. Somit ist der Graph 3-färbbar, da keine zwei verbundenen Knoten die gleiche Farbe haben.

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

Smith
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 13. Apr 2015 15:45

Re: Theorie 5 Aufgabe 2

Beitrag von Smith »

Danke Rolf!
Die Frage bestand wirklich nur solange ich mich noch nicht gut genug reingedacht hatte.
Aber sehr gut erklärt : )
Phil

Antworten

Zurück zu „Archiv“