Frage zu 5.1

NonStop
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 18. Apr 2015 19:15

Frage zu 5.1

Beitrag von NonStop »

Hallo,

soll man in der Aufgabe 1 den gesamten Graph zeichnen oder reicht es, wenn man für jede Variablle aus Klausel 1 einen eigenen Teilgraph zeichnet? Ich habe versucht einen gesamten zu zeichnen und der sieht total unübersichtlich aus, es sind zu viele Kanten, sodass man keine Cliquen ablesen kann.

Allerdings habe ich auch Kanten für Knoten der Art (x1,K1) und (x1,K3) gezeichnet. Ist das richtig so, oder soll man Kanten nur für Knoten für unterschiedliche Variablen aus unterschiedlichen Klauseln zeichnen?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Frage zu 5.1

Beitrag von Prof. Karsten Weihe »

Falls Sie diese Aufgabe als Vorbereitung auf die Klausur bearbeiten, machen Sie es sich doch im Zweifelsfall eher ein bisschen zu schwer als ein bisschen zu leicht. :wink:

Ihr Erfolg bei der Klausur wird nicht davon abhängen, wie die Formulierungen auf den Übungsblättern genau zu verstehen sind.

Oder habe ich Ihr Anliegen falsch verstanden?

KW

NonStop
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 18. Apr 2015 19:15

Re: Frage zu 5.1

Beitrag von NonStop »

Ich wollte nur wissen wie man richtig eine 3-CNF Formel auf einen Graph reduziert, für den Fall, wenn eine ähnliche Aufgabe in der Klausur vorkommt, denn wenn ich es genauso mache, wie es in den Folien steht, kommt ein seltsames Ergebnis raus :)

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Frage zu 5.1

Beitrag von Prof. Karsten Weihe »

NonStop hat geschrieben:Ich wollte nur wissen wie man richtig eine 3-CNF Formel auf einen Graph reduziert, für den Fall, wenn eine ähnliche Aufgabe in der Klausur vorkommt, denn wenn ich es genauso mache, wie es in den Folien steht, kommt ein seltsames Ergebnis raus :)
Aha, darauf wäre ich nicht gekommen, dass so etwas hinter Ihrer Frage steht. Was genau ist denn Ihr Problem mit den Folien?

KW

NonStop
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 18. Apr 2015 19:15

Re: Frage zu 5.1

Beitrag von NonStop »

Prof. Karsten Weihe hat geschrieben:
Aha, darauf wäre ich nicht gekommen, dass so etwas hinter Ihrer Frage steht. Was genau ist denn Ihr Problem mit den Folien?

KW
Wenn man die ganze KNF-Formel zeichnerisch in einen Graph umwandelt so wie es auf Folie 46 steht, dann muss man zwischen 9 Knoten 21 Kanten zeichnen, wobei sie sich oft schneiden unabhängig davon, wie man Knoten auf Papier platziert. So kann man sehr schlecht erkennen, welche Cliquen rausgekommen sind. Meine erste Frage war, ob man die Lösung zerteilen kann auf mehrere Teillösungen. Z.B. indem man für jede Variable aus Klausel 1 eigene Teilgraphen zeichnet und daraus die Cliquen abliest.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Frage zu 5.1

Beitrag von Prof. Karsten Weihe »

NonStop hat geschrieben: Meine erste Frage war, ob man die Lösung zerteilen kann auf mehrere Teillösungen. Z.B. indem man für jede Variable aus Klausel 1 eigene Teilgraphen zeichnet und daraus die Cliquen abliest.
Ok, ich denke, jetzt habe ich Sie verstanden. :)

Zwei Antworten:

1. Ich bin mir sicher, vor einer Frage ähnlicher Art werden Sie in der Klausur nicht stehen.

2. Jenseits der konkret anstehenden Klausur: Solange die Zerlegung einer Lösung in Teillösungen einfach und unzweideutig nachvollziehbar ist (ggf. mit Hilfe von Kommentaren), ist das bei von mir verantworteten Lehrveranstaltungen kein Problem.

Frage jetzt beantwortet?

KW

NonStop
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 18. Apr 2015 19:15

Re: Frage zu 5.1

Beitrag von NonStop »

Ja, danke für die klare Antwort :)

Antworten

Zurück zu „Archiv“