Cliquenproblem Das mit CLIQUE notiert ist ein Entscheidungsproblem der Graphentheorie Das ist eines der 21 klassischen N

Cliquenproblem

Das Cliquenproblem (mit CLIQUE notiert) ist ein Entscheidungsproblem der Graphentheorie. Das Cliquenproblem ist eines der 21 klassischen NP-vollständigen Probleme, deren Zugehörigkeit zu dieser Klasse Richard M. Karp 1972 bewies.

Problemstellung Bearbeiten

Es ist gefragt, ob es zu einem einfachen Graphen G und einer Zahl n eine Clique der Mindestgröße n in G gibt; das heißt, ob G zumindest n Knoten hat, die alle untereinander paarweise verbunden sind.

Satz Bearbeiten

CLIQUE ist NP-vollständig.

Beweisidee Bearbeiten

Polynomialzeitreduktion von 3KNF-SAT auf CLIQUE:

Da 3KNF-SAT NP-schwer ist, gilt dies dann auch für CLIQUE. Außerdem lässt sich leicht zeigen, dass CLIQUE selbst in NP liegt, insgesamt ist es also NP-vollständig.

Beweisskizze Bearbeiten

Sei F eine Formel mit n Klauseln in 3KNF, also in konjunktiver Normalform mit höchstens drei Literalen pro Klausel:

Aus F mit n Klauseln konstruieren wir einen Graphen G und zeigen dann: F ist erfüllbar genau dann, wenn G eine n-Clique besitzt.

Konstruktion von G Bearbeiten

Knoten von G seien sämtliche Literalvorkommen in der Formel F, genauer alle Paare .
Kanten von G seien sämtliche Verbindungen zwischen Literalvorkommen, ausgenommen allein
1. zwischen zwei Literalvorkommen in ein und derselben Klausel — also nicht und per Kante verbinden
2. zwischen zwei Literalvorkommen, in denen dasselbe Literal einmal positiv und einmal negiert auftritt — also nicht und verbinden, falls für ein k.

Beweis Bearbeiten

G besitzt eine n-Clique ⇒ F ist erfüllbar: Angenommen, G besitzt eine n-Clique. Den Literalen von in dieser Clique liegenden Literalvorkommen geben wir den Wahrheitswert wahr. Dies ist widerspruchslos wegen der 2. Kantenbedingung möglich. Weil nach der 1. Kantenbedingung keine zwei Literalvorkommen aus derselben Klausel per Kante verbunden sind, werden unter dieser Belegung alle n von n Klauseln von F wahr und damit auch F.
F ist erfüllbar ⇒ G besitzt eine n-Clique: Angenommen, F sei erfüllbar. Dann gibt es eine Wahrheitswertbelegung seiner Literale, so dass in jeder der Klauseln wenigstens ein Literal wahr wird. Wir wählen in jeder Klausel willkürlich genau ein Literalvorkommen mit wahrem aus. Alle diese bilden offenbar eine n-Clique in G.

Beispiele Bearbeiten

Beispiel für eine erfüllbare Belegung: Der konstruierte Graph.	Beispiel für eine nichterfüllbare Belegung: Der konstruierte Graph.
Es gibt sieben verschiedene 2-Cliquen im Graphen.	Es gibt keine einzige 3-Clique im Graphen.

Siehe auch Bearbeiten

Literatur Bearbeiten

Schöning, Uwe: Theoretische Informatik - kurzgefasst. - 4. Aufl., korr. Nachdr. - Heidelberg : Spektrum, Akad. Verl., 2003, ISBN 3-8274-1099-1.

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele

Veröffentlichungsdatum: Oktober 23, 2023, 05:51 am

Das Cliquenproblem mit CLIQUE notiert ist ein Entscheidungsproblem der Graphentheorie Das Cliquenproblem ist eines der 21 klassischen NP vollstandigen Probleme deren Zugehorigkeit zu dieser Klasse Richard M Karp 1972 bewies Inhaltsverzeichnis 1 Problemstellung 2 Satz 2 1 Beweisidee 2 2 Beweisskizze 2 3 Konstruktion von G 2 4 Beweis 3 Beispiele 4 Siehe auch 5 LiteraturProblemstellung BearbeitenEs ist gefragt ob es zu einem einfachen Graphen G und einer Zahl n eine Clique der Mindestgrosse n in G gibt das heisst ob G zumindest n Knoten hat die alle untereinander paarweise verbunden sind Satz BearbeitenCLIQUE ist NP vollstandig Beweisidee Bearbeiten Polynomialzeitreduktion von 3KNF SAT auf CLIQUE 3 K N F S A T p C L I Q U E displaystyle 3KNF SAT preceq p CLIQUE nbsp Da 3KNF SAT NP schwer ist gilt dies dann auch fur CLIQUE Ausserdem lasst sich leicht zeigen dass CLIQUE selbst in NP liegt insgesamt ist es also NP vollstandig Beweisskizze Bearbeiten Sei F eine Formel mit n Klauseln in 3KNF also in konjunktiver Normalform mit hochstens drei Literalen pro Klausel F y 1 1 y 1 a 1 y n 1 y n a n displaystyle F y 1 1 lor dotsc lor y 1 a 1 land dotsc land y n 1 lor dotsc lor y n a n nbsp mit 1 i n 1 a i 3 displaystyle text mit forall 1 leq i leq n 1 leq a i leq 3 nbsp und i j y i j x 1 x m x 1 x m displaystyle text und forall i j y i j in x 1 x m overline x 1 overline x m nbsp Aus F mit n Klauseln konstruieren wir einen Graphen G und zeigen dann F ist erfullbar genau dann wenn G eine n Clique besitzt Konstruktion von G Bearbeiten Knoten von G seien samtliche Literalvorkommen in der Formel F genauer alle Paare y i j i displaystyle y i j i nbsp Kanten von G seien samtliche Verbindungen zwischen Literalvorkommen ausgenommen allein zwischen zwei Literalvorkommen in ein und derselben Klausel also nicht y i j 1 i displaystyle y i j 1 i nbsp und y i j 2 i displaystyle y i j 2 i nbsp per Kante verbinden zwischen zwei Literalvorkommen in denen dasselbe Literal einmal positiv und einmal negiert auftritt also nicht y i 1 j 1 i 1 displaystyle y i 1 j 1 i 1 nbsp und y i 2 j 2 i 2 displaystyle y i 2 j 2 i 2 nbsp verbinden falls y i 1 j 1 y i 2 j 2 x k x k displaystyle y i 1 j 1 y i 2 j 2 x k overline x k nbsp fur ein k Beweis Bearbeiten G besitzt eine n Clique F ist erfullbar Angenommen G besitzt eine n Clique Den Literalen y i j displaystyle y i j nbsp von in dieser Clique liegenden Literalvorkommen y i j i displaystyle y i j i nbsp geben wir den Wahrheitswert wahr Dies ist widerspruchslos wegen der 2 Kantenbedingung moglich Weil nach der 1 Kantenbedingung keine zwei Literalvorkommen aus derselben Klausel per Kante verbunden sind werden unter dieser Belegung alle n von n Klauseln von F wahr und damit auch F F ist erfullbar G besitzt eine n Clique Angenommen F sei erfullbar Dann gibt es eine Wahrheitswertbelegung seiner Literale so dass in jeder der Klauseln wenigstens ein Literal wahr wird Wir wahlen in jeder Klausel willkurlich genau ein Literalvorkommen y i j i displaystyle y i j i nbsp mit wahrem y i j displaystyle y i j nbsp aus Alle diese bilden offenbar eine n Clique in G Beispiele BearbeitenBeispiel fur eine erfullbare Belegung x 1 x 1 x 2 x 2 x 1 x 2 displaystyle overline x 1 lor x 1 lor overline x 2 land x 2 lor x 1 lor overline x 2 nbsp nbsp Der konstruierte Graph Beispiel fur eine nichterfullbare Belegung x 1 x 1 x 2 x 2 x 2 x 1 x 2 x 2 x 2 displaystyle overline x 1 lor overline x 1 lor x 2 land x 2 lor x 2 lor x 1 land overline x 2 lor overline x 2 lor overline x 2 nbsp nbsp Der konstruierte Graph nbsp Es gibt sieben verschiedene 2 Cliquen im Graphen nbsp Es gibt keine einzige 3 Clique im Graphen Siehe auch BearbeitenKomplexitatsklasse NP Komplexitatsklasse Erfullbarkeitsproblem der Aussagenlogik SAT Literatur BearbeitenSchoning Uwe Theoretische Informatik kurzgefasst 4 Aufl korr Nachdr Heidelberg Spektrum Akad Verl 2003 ISBN 3 8274 1099 1 Karps 21 NP vollstandige Probleme Erfullbarkeitsproblem der Aussagenlogik Cliquenproblem Mengenpackungsproblem Knotenuberdeckungsproblem Mengenuberdeckungsproblem Feedback Arc Set Feedback Vertex Set Hamiltonkreisproblem Integer Linear Programming 3 SAT graph coloring problem Covering by cliques Problem der exakten Uberdeckung 3 dimensional matching Steinerbaumproblem Hitting set Rucksackproblem Job sequencing Partitionsproblem Maximaler Schnitt Abgerufen von https de wikipedia org w index php title Cliquenproblem amp oldid 170252630