 Cliquenproblem in NP |
Ina
Grünschnabel
Dabei seit: 15.01.2011
Beiträge: 1
 |
|
Meine Frage:
Hallo!
Ich muss beweisen, dass das Cliquenproblem NP-vollständig ist. NP-Härte habe ich schon bewiesen, aber mein Beweis dafür, dass es in NP ist hinckt und ich hätte auch gerne ein Beispiel für einen Graphen, der es erfüllt.
Cliquenproblem:
Gegeben ist ein Graph G=(V,E) und eine natürliche Zahl k. Gibt es eine Clique der Größe k in G?
Clique: Zusammenhängender Teilgraph; je zwei Knoten sind miteinander verbunden.
Meine Ideen:
Hat man eine Teilmenge von V erraten, für die gilt, dass die Größe der Teilmenge = k ist, ist es offensichtlich, dass man sein Ergebnis in ploynomieller Zeit verifizieren kann.
Zumindest empfinde ich das so. Allerdings ist das noch kein wirklicher Beweis, dass es so ist und ein Bsp. wäre auch nicht schlecht...
|
|
15.01.2011 02:12 |
|
|
Ibn Batuta 
Mitglied
Dabei seit: 02.01.2011
Beiträge: 26
|
|
Sagt dir 3SAT etwas? Wenn ja, reduziere es auf 3SAT. Dann ist der Beweis nicht so schwer.
Ibn Batuta
|
|
|
16.01.2011 19:30 |
|
|
Hubert1965
Grünschnabel
Dabei seit: 26.02.2011
Beiträge: 8
|
|
Wenn ich mich nicht sehr irre, ist ein Problem exakt genau dann NP-vollständig, wenn es einen Algorithmus gibt, mit dem die Parameter dieses Problems in polynomieller Zeit in die Parameter eines anderen Problems umgewandelt werden können, von dem bereits bekannt ist, dass es NP-vollständig ist.
Es gibt derzeit 21 Probleme, für die die NP-vollständigkeit bereits beweisen ist: http://de.wikipedia.org/wiki/Karps_21_NP...ndige_Probleme. Das Cliquen-Problem ist in dieser Liste enthalten. Wenn es dir gelingt, dieses Problem z.B. auf http://de.wikipedia.org/wiki/Erfüllbarke...r_Aussagenlogik zurückzuführen, hast du den Beweis erbracht.
|
|
|
26.02.2011 20:03 |
|
|
|
