Graphentheorie beweis < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < 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,
hat jmd viellecht einen Beweis dafuer?
|
|
| |
|
> 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,
> hat jmd viellecht einen Beweis dafuer?
Solange der Graph noch kein Baum ist, also noch
mindestens einen "Kreis" enthält, kann man aus
einem der Kreise eine Kante entfernen, ohne dabei
den Zusammenhang zu zerstören oder Ecken zu
isolieren. Bei jedem solchen Schritt vermindert
sich die Anzahl der Kanten um 1. Das macht man
so lange, bis kein Kreis mehr vorhanden ist und
der Teilgraph T erreicht ist. Da der Graph G endlich
sein soll, muss dieses Verfahren terminieren, denn
man kann ja auch nur eine endliche Zahl von
Kanten entfernen.
LG al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:57 Fr 13.06.2008 | | Autor: | Lessequal |
danke danke :)
|
|
|
| |
|
Hallo,
bitte keine Doppelpostings mehr in Zukunft!
Gruß v. Angela
|
|
|
|
