NP Vollständigkeit < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeige die NP-Vollständigkeit der folgenden Probleme:
a) TSP Entscheidungsproblem
b)u-v-Hamilton Pfad
c)HamiltonPfad
d) alle Probleme auf gerichteten Graphen
Tipp Es darf vorrausgesetzt werden, dass der Hamilton Kreis über ungerichtete Graphen NP-vollständig ist. |
Anmerkung: Wir haben die Probleme mit ungerichten Graphen definiert und das TSP mit einem vollständigen Graphen.
Hier meine Lösung:
a)Frage: Gibt es in G=(V,E) einen einfachen Kreis durch alle Knoten der Länge K [mm] \leq [/mm] K?
Antwort: Die Frage kann umformuliert werden in : Gibt es in G einen hamiltonschen Kreis der Länge K?
Man könn nun einen Graphen mit Kantenbewertung auf einen Graphen bringen, der auf jeder Kante 1 hat, falls si existiert und falls sie in G nicht existiert, ich weiß aber nicht, ob das nötig ist, da wir die Länge ja grade über die Kantenbewertung c rausbekommen.
Wenn nun ein Hamiltonkreis im Graphen existiert ist die Frage ob seine Länge kleiner K ist in polynomieller Zeit ausführbar.
So lässt sich das TSP in einen Hamilton Kreis Problem transformieren und deswegen ist es in NP.
(Allerdings kann ja dann die antwort auf Hamiltonschen Kreis "ja" und die Antwort auf die Länge [mm] \leq [/mm] K "nein" sein und dann sind die Probleme doch nicht mehr äquivalent, oder?)
b) Frage: Enthalt G einen Hamiltonweg der bei u startet und bei v endet?
Antwort: Wenn u und v adjazent sind können wir das Problem wieder über Hamiltonsche Kreise lösen, indem wir Fragen: Existiert ein Hamiltonscher Kreis, der in u anfängt(und dessen vorletzter Knoten v ist)?
Wenn ja wird dieser Kreis übergeben und die letzte Kante gelöscht -> tadaa Hamiltonscher Pfad mit Anfangspunkt u und Endknotn v.
Problem: Was ist wenn u und v nicht benachbart sind? Ein hamiltonscher Weg von u nach v kann dann doch trotzdem existieren, oder?
c) Frage: Enthalt G einen Hamiltonpfad?
Antwort: Folgender kleiner Algorithmus dazu:
1)Suche Hamiltonpfad
2)Lösche letze Kante im Kreis
3) Gib Hamiltonpfad zurück.
Da Schritt 2 und 3 in polynomieller Zeit ausführbar sind ist das eine transformation vom Hamilton Pfad zum HamiltonKreis und damit in NP
Aber auch hier: Kann es nicht auch HamiltonPfade geben, wenn es keine HKreise gibt?
d) Durch ersetzen der ungerichteten Kanten durch zweich entgegengestzt gerichtete Kanten(dieser austausch ist polynomiell) transformiert man die Probleme in die oben genannt(bewiesenen) Probleme, deswegen sind sie dann NP vollständig.
Was aber passiert wenn ein Grapg gerichtet ist und es zwischen zwei Knoten nur einen Weg gibt weiß ich leider nicht.
Ich hoffe, dass ihr mit trotz meines langen Textes helfen könnt.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Viele Grüße MatheJeany
|
|
| |
|
> Zeige die NP-Vollständigkeit der folgenden Probleme:
> a) TSP Entscheidungsproblem
> b)u-v-Hamilton Pfad
> c)HamiltonPfad
> d) alle Probleme auf gerichteten Graphen
vermutlich alle oberen Probleme auf gerichteten Graphen.
>
> Tipp Es darf vorrausgesetzt werden, dass der Hamilton Kreis
> über ungerichtete Graphen NP-vollständig ist.
>
> Anmerkung: Wir haben die Probleme mit ungerichten Graphen
> definiert und das TSP mit einem vollständigen Graphen.
>
> Hier meine Lösung:
> a)Frage: Gibt es in G=(V,E) einen einfachen Kreis durch
> alle Knoten der Länge K [mm]\leq[/mm] K?
Die Ungleichung ist ohne Nachdenken hingetippt. Sie gilt immer.
> Antwort: Die Frage kann umformuliert werden in : Gibt es
> in G einen hamiltonschen Kreis der Länge K?
Was ist K?
> Man könn nun einen Graphen mit Kantenbewertung auf einen
> Graphen bringen, der auf jeder Kante 1 hat, falls si
> existiert und falls sie in G nicht existiert, ich weiß
Mit was möchtest du sie belegen, wenn sie nicht existiert?
> aber nicht, ob das nötig ist, da wir die Länge ja grade
> über die Kantenbewertung c rausbekommen.
> Wenn nun ein Hamiltonkreis im Graphen existiert ist die
> Frage ob seine Länge kleiner K ist in polynomieller Zeit
> ausführbar.
> So lässt sich das TSP in einen Hamilton Kreis Problem
> transformieren und deswegen ist es in NP.
>
> (Allerdings kann ja dann die antwort auf Hamiltonschen
> Kreis "ja" und die Antwort auf die Länge [mm]\leq[/mm] K "nein"
> sein und dann sind die Probleme doch nicht mehr
> äquivalent, oder?)
Wenn man es richtig macht, so lässt sich eine Reduktion angeben.
Das ist alles etwas ungenau. Du willst so eine many-to-one Reduktion basteln, d.h.
Hamiltonkreis [mm] $\le_p$ [/mm] TSP.
Also sei G=(V,E) ein Graph aus der Problemstellung des Hamiltonkreises mit n=|V|. Jetzt möchtest du das Problem vom Hamiltonkreis mittel TSP lösen. Die Gewichtung der Kanten ist gut angesetzt. Falls eine Kante im Graphen existiert so setzt man das Gewicht der Kante im abgeänderten Grapgen G' auf 1 und andernfalls auf 2.
Dann gibt es einen Hamiltonkreis <=> eine Rundreise der Länge .... existiert.
>
> b) Frage: Enthalt G einen Hamiltonweg der bei u startet und
> bei v endet?
> Antwort: Wenn u und v adjazent sind können wir das
> Problem wieder über Hamiltonsche Kreise lösen, indem wir
> Fragen: Existiert ein Hamiltonscher Kreis, der in u
> anfängt(und dessen vorletzter Knoten v ist)?
> Wenn ja wird dieser Kreis übergeben und die letzte Kante
> gelöscht -> tadaa Hamiltonscher Pfad mit Anfangspunkt u
> und Endknotn v.
Richtig!
>
> Problem: Was ist wenn u und v nicht benachbart sind? Ein
> hamiltonscher Weg von u nach v kann dann doch trotzdem
> existieren, oder?
Dann füge eine künstliche Kante zwischen u und v ein und du bist in der Situation, die du lösen konntest.
>
>
> c) Frage: Enthalt G einen Hamiltonpfad?
> Antwort: Folgender kleiner Algorithmus dazu:
> 1)Suche Hamiltonpfad
Eher Suche Hamiltonkreis
> 2)Lösche letze Kante im Kreis
> 3) Gib Hamiltonpfad zurück.
> Da Schritt 2 und 3 in polynomieller Zeit ausführbar sind
> ist das eine transformation vom Hamilton Pfad zum
> HamiltonKreis und damit in NP
>
> Aber auch hier: Kann es nicht auch HamiltonPfade geben,
> wenn es keine HKreise gibt?
Es gibt doch im Wesentlichen nur ein Hamiltonpfad. Wie soll so ein Fall aussehen, der dir Kopfschmerzen macht?
>
> d) Durch ersetzen der ungerichteten Kanten durch zweich
> entgegengestzt gerichtete Kanten(dieser austausch ist
> polynomiell) transformiert man die Probleme in die oben
> genannt(bewiesenen) Probleme, deswegen sind sie dann NP
> vollständig.
> Was aber passiert wenn ein Grapg gerichtet ist und es
> zwischen zwei Knoten nur einen Weg gibt weiß ich leider
> nicht.
Ich glaube, dass du immer die Richtungen verdrehst.
d) heißt mit anderen Worten: Wenn man ein Problem im ungerichteten Graphen auf eines im gerichteten Fall reduzieren kann, dann ist es auch im gerichteten Graphen NP-vollständig.
Man möchte also zeigen, dass ein Problem im gerichteten Graphen NP-vollständig ist. Wenn man nun vom selbige Problem die NP-vollständigkeit im ungerichteten Falls kennt, muss man nur in die eine Richtung den ungerichten Graphen in einen gerichteten Graphen, wie du schriebst, umwandeln.
>
>
> Ich hoffe, dass ihr mit trotz meines langen Textes helfen
> könnt.
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Viele Grüße MatheJeany
Noch ein paar Sachen, die vielleicht fehlen. Die Reduktionen, sprich die Transformationen, müssen in Polynomialzeit berechenbar sein. Man sollte soetwas zumindest erwähnen. Bei c) hast du es ja gemacht. Aber bei a), b) und d) fehlt es.
Desweiteren solltest du ja zeigen, dass die Probleme NP-vollständig sind. Dazu gehört in jedem Fall auch kurz zu begründen, dass die in NP liegen. Liegen Sie nicht in NP, so können sie auch nicht NP-vollständig sein.
Bei mir hattes es immer gereicht kurz zu schreiben, dass eine entsprechende NTM gibt und das auch kurz zu begründen.
gruß
wieschoo
|
|
|
|
