Beweis für Bäume < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:57 So 20.02.2011 | | Autor: | hilado |
| Aufgabe | | Beweisen oder widerlegen Sie: Ein Graph G = (V, E) ist genau dann ein Baum, wenn jeder Knoten Grad mindestens 1 hat und für die Summe aller Knotengrade gilt $ [mm] \summe_{v \in V} [/mm] deg(v) = 2(|V| - 1) $ |
deg(v) ist die Gradzahl eines Knotens.
In der Lösung steht, dass die Richtung => klar ist, weil ein Baum zusammenhängend ist und $ |V| - 1 $ Kanten hat. Doch die andere Richtung ist falsch mit der Begründung der zwei unten gezeigten Bilder. Doch das zweite Bild ist doch eigentlich kein Baum, oder?:
forum-i00771563-n001.jpg
forum-i00771563-n002.jpg
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
Anhang Nr. 2 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:14 So 20.02.2011 | | Autor: | qsxqsx |
Hallo,
1. Ja, das zweite Bild ist kein Baum.
2. Mit zwei Bildern bzw. Beispielen hat du noch lange nichts bewiesen. Beweisen heisst allgemein zu Zeigen was gelten soll.
Jeder Baum hat eine Wurzel. Fang dort an und frag dich wies aussieht wenn du was wie anfügst.
Gruss
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:27 So 20.02.2011 | | Autor: | hilado |
Angenommen, ich habe nur einen Knoten. Also |V| = 1. Und ich habe hier folgenden Satz:
Ist T = (V, E) ein Baum , dann gilt |E| = |V| - 1.
Dann kann ich doch davon ausgehen, dass ein einzelner Knoten an sich auch ein Baum ist, nur halt ohne Blätter. Kann ich das so annehmen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:34 So 20.02.2011 | | Autor: | qsxqsx |
Ja.
1 Knoten und 0 Kanten --> In die Formel einsetzen: 0 = 1 - 1 ---> korrekt ---> ist Baum.
PS: Wenn du die Formel E = V - 1 benutzen darfst, ist der Beweis noch einfacher. Du musst dir nur überlegen, was gelten muss für einen allgemeinen Graphen für die Knotengradsumme und die Kanten?
Gruss
|
|
|
|
