Graphentheorie < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Zeigen sie,dass folgendes Lemma gilt
Fuer jeden ungerichteten,endlichen,zusammenhaengenden graphen G gibt es einen Teilgraph T ,der ein Baum ist und fuer den [mm] V_{T} [/mm] = [mm] V_{G} [/mm] gilt.
|
hallo,
kann mir jmd sagen wie der Beweis geht?
|
|
| |
|
Hallo Lessequal!
> Zeigen sie,dass folgendes Lemma gilt
>
> Fuer jeden ungerichteten,endlichen,zusammenhaengenden
> graphen G gibt es einen Teilgraph T ,der ein Baum ist und
> fuer den [mm]V_{T}[/mm] = [mm]V_{G}[/mm] gilt.
>
> hallo,
>
> kann mir jmd sagen wie der Beweis geht?
Wie man das am besten beweist, weiß ich nicht, aber die Aussage ist doch klar, oder? Man könnte es vielleicht algorithmisch zeigen, indem man jede Kante betrachtet und schaut, ob sie auf einem Kreis liegt und falls ja, dass man sie dann entfernt. Hat man alle Kreise entfernt, hat man einen Baum.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Schau dir doch einfach mal Minimal-Spanning-Trees an - das sind genau solche Bäume. 
|
|
|
|
