Fehler im Induktionsbeweis < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:47 Fr 22.05.2009 | | Autor: | Audience |
| Aufgabe | Behauptung: In einem ungerichteten, zusammmenhängenden Graphen G = (V, E) existiert ein Weg, der jeden Knoten genau einmal besucht.
Beweis: Induktion nach |V| = n.
Für n = 1 gilt die Behauptung.
Sei nun G' = (V', E') ein Graph mit n Knoten, der einen Weg, [mm] v_{1}v_{2}...v_{n} [/mm] besitzt, der jeden Knoten genau einmal besucht. Wir konstruieren daraus einen Graphen G = (V, E) mit n+1 Knoten, indem wir einen Knoten [mm] v_{n+1} [/mm] und die Kante [mm] {v_{n},v_{n+1}} [/mm] hinzufügen. Der entstandene Graph erfüllt die Behauptung.
Wo ist der Fehler in diesem Beweis?
|
Hallo,
ich glaube, den Fehler gefunden zu haben, bin mir aber wegen der Formulierung nicht ganz sicher. Meiner Meinung nach scheitert der Beweis daran, dass nur gezeigt wird, dass man für jedes n einen Graphen konstruieren kann, in dem ein solcher Weg existiert (was in diesem Falle ja eine Liste wäre). Eigentlich müsste gezeigt werden, dass jeder Graph aus n+1 Knoten bestehend in einen Graphen mit n Knoten zerlegt werden könnte und dass von diesem Graphen aus es einen Weg zur neuen Kante [mm] v_{n+1} [/mm] gibt.
Sind meine Gedanken so richtig? Wie kann man das kürzer formulieren?
Gruß,
Thomas
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:58 Fr 22.05.2009 | | Autor: | pelzig |
> ich glaube, den Fehler gefunden zu haben, bin mir aber
> wegen der Formulierung nicht ganz sicher. Meiner Meinung
> nach scheitert der Beweis daran, dass nur gezeigt wird,
> dass man für jedes n einen Graphen konstruieren kann, in
> dem ein solcher Weg existiert (was in diesem Falle ja eine
> Liste wäre). Eigentlich müsste gezeigt werden, dass jeder
> Graph aus n+1 Knoten bestehend in einen Graphen mit n
> Knoten zerlegt werden könnte und dass von diesem Graphen
> aus es einen Weg zur neuen Kante [mm]v_{n+1}[/mm] gibt.
>
> Sind meine Gedanken so richtig? Wie kann man das kürzer
> formulieren?
Genau, Im Induktionsschritt werden nicht alle Graphen mit n+1 Knoten erfasst, z.B. einen mit 4 Knoten, der wie ein "Y" aussieht.
Gruß, Robert
|
|
|
|
