www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Graphentheorie" - NP Vollständigkeit
NP Vollständigkeit < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

NP Vollständigkeit: Korrektur und Hilfe
Status: (Frage) beantwortet Status 
Datum: 16:01 Sa 10.11.2012
Autor: MatheJeany

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

        
Bezug
NP Vollständigkeit: Antwort
Status: (Antwort) fertig Status 
Datum: 12:22 So 11.11.2012
Autor: wieschoo


> 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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de