T5 Aufgabe 1

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

T5 Aufgabe 1

Beitrag von AlexIschuk »

Hallo,

gibt es eine Beziehung zwischen der Anzahl der erfuellenden Belegnungen einer Formel in 3-CNF und der Anzahl der k-Cliquen in einem Graphen?
(Ich habe bspw. bei der ersten Aufgabe viel mehr Cliquen als ich erfuellende Belegungen habe.)
Bzw. was genau bedeutet die Beobachtung im Foliensatz "Komplexitaet algorithmischer Probleme" S.48 : "Beobachtung: Die erfüllenden Variablenbe-
legungen entsprechen den k-Cliquen in G." ?

Vielen Dank
Gruss
Alex

Sheldon
Erstie
Erstie
Beiträge: 20
Registriert: 23. Apr 2015 17:08

Re: T5 Aufgabe 1

Beitrag von Sheldon »

Die Beobachtung beinhaltet genau die Antwort auf deine gestellte Frage. Wenn du in der booleschen Formel n erfüllende Belegungen findest, dann sollten in dem von dir erstellten Graphen ebenfalls genau n 3-Cliquen existieren, welche den o.g. Belegungen entsprechen. Wenn das bei dir nicht der Fall ist, dann solltest du nochmal deinen Graphen überprüfen.

Gruß Sheldon

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

Re: T5 Aufgabe 1

Beitrag von AlexIschuk »

Wie versteh ich dann das Beispiel auf Wikipedia dazu (https://de.wikipedia.org/wiki/Cliquenproblem)? Im ersten Beispiel ist eine 3-CNF mit 2 Klauseln und der dazugehoerige Graph gezeigt. Diese Formel ist fuer alle Belegungen der 2 Eingangsvariablen wahr (Tautologie). Insgesamt gibt es nur 4 moegliche Belegungen der 2 Variablen, aber es gibt 7 Cliquen. Das ist ja auch logisch, da dieselben Variablen in meheren Klauseln vorkommen koennen und man diese verbinden muss.

Man kann ja auch mehrere Cliquen mit denselben Literalen im Graphen erhalten. Aber ich nehme an, dass das als eine Clique zaehlt.

Sheldon
Erstie
Erstie
Beiträge: 20
Registriert: 23. Apr 2015 17:08

Re: T5 Aufgabe 1

Beitrag von Sheldon »

Jetzt verstehe ich dein Problem. Also an sich gibt es wohl im Allgemeinen immer mehr k-Cliquen im zugeordneten Graphen als mögliche Belegungen in der booleschen Formel. Das ist den Regeln der Konstruktion des Graphen geschuldet. Deine ursprünglische Frage zielte aber auf die erfüllenden Belegungen, und für jede dieser erfüllenden Belegungen gibt es jeweils ein Gegenstück in Form einer Clique im Graphen. Die Anzahl dieser speziellen Cliquen ist aber nicht gleich der Gesamtanzahl aller Cliquen.

Ob es eine eindeutige Beziehung zwischen der Anzahl der erfüllenden Belegungen und der Anzahl aller möglichen k-Cliquen im Graphen gibt, weiß ich nicht. Ich weiß aber auch nicht, wozu man diese Information benötigt.

Clemens Krug
Neuling
Neuling
Beiträge: 3
Registriert: 16. Mai 2015 17:23

Re: T5 Aufgabe 1

Beitrag von Clemens Krug »

Aber auch wenn man nur die erfüllenden Belegungen betrachtet, gibt es mehr Cliquen also Belegungen?!?

Z.B. ist die Belegung x1=true, x2=false, x3=false erfüllend. Allerdings lassen sich daraus die Cliquen

(x1, K1),(x3', K2), (x2', K3) und

(x2', K1),(x3', K2), (x1, K3) bilden. (Negierte mit ' dargestellt).

Wie ist das zu verstehen?

Hallo
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 22. Apr 2015 19:03

Re: T5 Aufgabe 1

Beitrag von Hallo »

Hallo,

Ich habe den Graph konstruiert, jedoch habe ich eine Frage zu den Erfüllenden Bedingungen.

Ich habe es so verstanden, da die Erfüllende Bedingungen, die sind, in der mindestens einmal 1 vorkommt (bspl: 0 0 1, 1 0 0, 0 1 0) und einmal dass alle 1 sind ( 1 1 1).

Habe ich das richtig verstanden?

UPDATE: Frage in anderen Forum geklärt. :)

Viele Grüße.

Antworten

Zurück zu „Archiv“