Eulerformel < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:43 Sa 03.05.2008 | | Autor: | Wimme |
| Aufgabe | Nehmen wir an, die Eulerformel v-e+f=c sei für Bäume (zusammenhängend, ungerichtet, zykelfrei) richtig.
Beweisen Sie die Formel nun für zusammenhängende Graphen und e>=1 durch Induktion über e. Verwenden Sie dabei im IS, dass sie für Bäume gilt. (v=knoten, e = Kanten, f = Facetten, c=Komponenten) |
Hi!
Hier mein Lösungsversuch:
I.A. e=1. Gibt es nur eine Kante, muss es zwei Knoten geben. Kein Zykel ist mögich => f=0. Damit ist die Formel richtig (beachte: wir betrachten zusammenhängende Graphen).
I.V. Gelte v-e+f=c für e=n
I.S. n -> n+1
v-e-1+f=1
Der Graph kann nun kein Baum mehr sein, denn dann würde die Formel für Bäume nicht mehr gelten. D.h. es gibt mind. einen Zykel und f>=1.
Für jede hinzugefügte Kante entsteht genau ein Zykel, deswegen stimmt die Gleichung.
Tja, mein Induktionsschritt ist kacke. Wenn ich in der I.V. schreiben könnte, dass der Graph ein Baum war, dann ist es ja nicht mehr so schwer, denke ich. Aber wenn ich das in die IV aufnehme, ist die Induktion doch blöd, oder?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:28 Mo 05.05.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
