P und NP (6) < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 13:47 Di 14.02.2006 | | Autor: | mathiash |
| Aufgabe | Es sei G=(V,E) ein ungerichteter Graph. Eine Clique von G ist eine Teilmenge [mm] K\subseteq [/mm] V der Knotenmenge V von G, so daß je zwei Knoten von K durch eine Kante in G verbunden sind (formal: [mm] P_2(K)\subseteq [/mm] E, wobei allgemein zu einer Menge X [mm] P_k(X)=\{U\subseteq X\: |\:\:\: |U|=k\} [/mm] die Menge aller k-elementigen Teilmengen von X bezeichne, also sind
Kanten des Graphen zweielementige Teilmengen der Knotenmenge V).
Das folgende Problem CLIQUE ist eines der bekannten NP-vollständigen Probleme und wurde in einer früheren Aufgabe schon vorgestellt:
Ggegeben ein Graph G=(V,E) und eine Zahl k, gibt es in G eine Clique der Größe k ?
Wir nehmen an, es gäbe eine Polynomzeit-Algorithmus, um in einem Graphen eine Clique zu finden, die stets
mindestens halb so groß ist wie die maximale Clique.
(a) Zeige: Dann gibt es einen Polynomzeit-Algorithmus, um eine Clique zu finde3n, die stets [mm] \frac{1}{\sqrt{2}} [/mm] - mal so groß ist wie die maximale Clique.
(b) Zeige: Es gibt dann sogar zu jedem k<1 einen Polyzeit-Algorithmus [mm] A_k, [/mm] um eine Clique zu finden, die
mindestens k-mal so groß ist wie die maximale Clique. |
Hallo zusammen,
noch etwas Standard-Stoff zum thema NP-Vollständigkeit. Hinweis: Formal müßte man ''die maximale Clique'' jeweils durch ''eine maximale Clique'' ersetzen, da es mehrere solche geben kann.
Viel Spass,
Mathias
|
|
|
