imported>Docosanus: /* Literatur */ Link Uwe Schöning

2025-12-13T13:03:57Z

Literatur: Link Uwe Schöning

Neue Seite

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

== Problemstellung ==

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

== Satz ==
CLIQUE ist [[NP-Vollständigkeit|NP-vollständig]].

=== Beweisidee ===
[[Polynomialzeitreduktion]] von [[3-SAT|3KNF-SAT]] auf CLIQUE:
:<math>{3KNF-SAT} \preceq_p CLIQUE</math>
Da 3KNF-SAT [[NP-Schwere|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 ===
Sei F eine Formel mit n Klauseln in 3KNF, also in konjunktiver Normalform mit höchstens drei [[Literal#Literale in der mathematischen Logik|Literal]]en pro Klausel:
:<math>F = (y_{1,1} \lor \dotsc \lor y_{1,a_1}) \land \dotsc \land (y_{n,1} \lor \dotsc \lor y_{n,a_n})</math>
:<math>\text{mit}\ \ \forall_{1 \le i \le n} : 1 \le a_i \le 3</math>
:<math>\text{und}\ \ \forall_{i, j} : y_{i,j} \in \{x_1,...,x_m, \overline{x_1},...,\overline{x_m}\}</math>.

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 ===
* Knoten von G seien sämtliche Literalvorkommen in der Formel F, genauer alle Paare <math>(y_{i,j}, i)</math>.
* Kanten von G seien sämtliche Verbindungen zwischen Literalvorkommen, ausgenommen allein
*# zwischen zwei Literalvorkommen in ein und derselben Klausel — also nicht <math>(y_{i,j_1}, i)</math> und <math>(y_{i,j_2}, i)</math> per Kante verbinden
*# zwischen zwei Literalvorkommen, in denen dasselbe Literal einmal positiv und einmal negiert auftritt — also nicht <math>(y_{i_1,j_1}, i_1)</math> und <math>(y_{i_2,j_2}, i_2)</math> verbinden, falls <math>\{y_{i_1,j_1}, y_{i_2,j_2} \} = \{x_k,\overline{x_k}\}</math> für ein k.

=== Beweis ===
* '''G besitzt eine n-Clique ⇒ F ist erfüllbar:''' Angenommen, G besitzt eine n-Clique. Den Literalen <math>y_{i,j}</math> von in dieser Clique liegenden Literalvorkommen <math>(y_{i,j}, i)</math> 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 <math>(y_{i,j}, i)</math> mit ''wahrem'' <math>y_{i,j}</math> aus. Alle diese bilden offenbar eine n-Clique in G.

== Beispiele ==

{|width="100%"
!valign="top" | Beispiel für eine erfüllbare Belegung:

<math>(\overline{x_1} \lor x_1 \lor \overline{x_2}) \land (x_2 \lor x_1 \lor \overline{x_2}) </math>

[[Datei:clique_ja2neu.PNG|framed|center|Der konstruierte Graph.]]

!valign="top"| Beispiel für eine nichterfüllbare Belegung:

<math>(\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})</math>

[[Datei:clique_nein2neu.PNG|framed|center|Der konstruierte Graph.]]
|-
|[[Datei:clique_ja.PNG|framed|center|Es gibt sieben verschiedene 2-Cliquen im Graphen.]]
|[[Datei:clique_nein.PNG|framed|center|Es gibt keine einzige 3-Clique im Graphen.]]
|}

== Siehe auch ==
* [[Komplexitätsklasse]]
* [[NP (Komplexitätsklasse)]]
* [[Erfüllbarkeitsproblem der Aussagenlogik|Erfüllbarkeitsproblem der Aussagenlogik (SAT)]]

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

{{Navigationsleiste Karps 21 NP-vollständige Probleme}}

[[Kategorie:Komplexitätstheorie]]

Cliquenproblem - Versionsgeschichte

imported>Docosanus: /* Literatur */ Link Uwe Schöning