|
|
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...
|
|
