NP-vollständigkeit zeigen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Sei k ≥ 2 eine Konstante. Beweisen Sie, daß es NP-vollständig ist zu entscheiden, ob ein gegebener ungerichteter Graph G einen aufspannenden Baum T enthält, in dem kein Knotengrad größer als k ist. |
Gegeben sei eine Instanz wie in der Aufgabe. Sei zusätzlich eine Lösung für diese Instanz gegeben. Das diese Lösung in polynomieller Zeit verifizierbar ist ist klar. (Prüfe ob der in der Lösung gegebene Baum zusammenhängend ist, alle Knoten aus V(G) enthält und ob alle Knoten Grad kleiner oder gleich haben).
Für den Fall k=2 sehe ich, dass man das Hamilton-Kreis-Problem hierauf reduzieren kann. (In einem Hamiltonkreis haben alle Knoten Grad 2).
Was mache ich aber im Falle k>2?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Mi 26.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
