Graph und Spannbaum < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Begründen oder widerlegen Sie folgende Behauptung:
Gegeben sei ein ungerichteter zusammenhängender Graph G und ein Spanning Tree T für G. Dann ist jede Kante von G, die nicht zu T gehört, Teil eines Zyklus in G. |
Hallo allerseits!
Ich sitze grad vor diesem Beweis. Könnte ich nicht argumentieren, dass ein Spanning Tree keinen Zyklus hat und somit jede zusätzliche Kante Teil eines Zyklus in G ist?!?!
Ich hoffe ihr könnt mir bei diesem Beweis etwas nachhelfen!
Mfg
chrissi
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:24 Mi 18.02.2009 | | Autor: | felixf |
Moin chrissi
> Begründen oder widerlegen Sie folgende Behauptung:
> Gegeben sei ein ungerichteter zusammenhängender Graph G
> und ein Spanning Tree T für G. Dann ist jede Kante von G,
> die nicht zu T gehört, Teil eines Zyklus in G.
>
> Hallo allerseits!
>
> Ich sitze grad vor diesem Beweis. Könnte ich nicht
> argumentieren, dass ein Spanning Tree keinen Zyklus hat und
> somit jede zusätzliche Kante Teil eines Zyklus in G
> ist?!?!
Warum sollte es denn ploetzlich einen Zyklus geben nur weil vorher keiner da war? Das musst du schon etwas mehr begruenden.
> Ich hoffe ihr könnt mir bei diesem Beweis etwas
> nachhelfen!
Ist dir die Aussage anschaulich klar? Nimm dir einen Spannbaum (oder irgendeinen Baum) und verbinde zwei Ecken, die vorher keine Kante dazwischen hatte. Was passiert?
(Betrachte erstmal zusammenhaengende Graphen -- dann ist der Spannbaum auch zusammenhaengend. Wenn der Graph nicht zusammenhaengend ist geht's genauso -- man muss nur ein kleines bisschen mehr denken :) )
LG Felix
|
|
|
|
