Ausgewogene Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Also ich habe hier folgende Definition vorliegen:
Ein Graph $H$ heißt ausgewogen, wenn für alle seine Teilgraphen [mm] $H`\subset [/mm] H$ gilt:
[mm] $\overline{d}(H`) \le \overline{d}(H)$
[/mm]
wobei mit [mm] $\overline{d}(H)$ [/mm] der Durchschnittsgrad von $H$ gemeint ist.
Im Speziellen beschäftige ich mich grade mit dem Satz von Erdös & Renji falls den jemand kennt. Der Inhalt dieses Satzes ist aber grade nicht so wichtig. Jedenfalls wird dieser Satz dann in einem Korollar auf Bäume (also zusammenhängende, kreisfreie Graphen) angewendet und hierfür braucht man als Voraussetzung, dass diese ausgewogen sind. |
Wenn ich den Begriff der Ausgewogenheit richtig verstanden habe, sind Bäume aber doch i. A. nicht ausgewogen, oder?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo,
mittlerweile habe ich die Antwort gefunden. Vielleicht bringts ja irgendwem was, also führe ich das hier kurz aus:
Bäume sind ausgewogen!
Zum Beweis hiervon braucht man die Aussage, dass für jeden Graph $G=(V,E)$ mit Knotenanzahl $|V|=n$ und Kantananzahl $|E|=m$ gilt:
[mm] $\summe_{v \in V} [/mm] d(v) = 2m$,
wobei mit $d(v)$ wiederum wie oben der Grad von $v [mm] \in [/mm] V$, also die Anzahl der inzidierenden Kanten gemeint ist.
Hieraus ergibt sich mit gleicher Definition wie oben:
[mm] $\overline{d}(G) [/mm] = [mm] \bruch{1}{|V|} \summe_{v \in V} [/mm] d(v) [mm] =\bruch{2m}{n}$
[/mm]
Sei nun $T$ ein beliebiger Baum mit $k$ Knoten, dann hat $T$ wegen der Kreisfreiheit und des Zusammenhangs $k-1$ Kanten, woraus folgt:
[mm] $\overline{d}(T) [/mm] = [mm] \bruch{2(k-1)}{k}$
[/mm]
Betrachtet man nun einen beliebigen Teilgraphen $H$ von $T$, der genau einen Knoten weniger besitzt. so verliert $H$ wegen des Zusammenhangs mindestens eine Kante, woraus folgt:
[mm] $\overline{d}(H) \le \bruch{2(k-2)}{k-1}$
[/mm]
Deshalb gilt:
[mm] $\overline{d}(H) \le \overline{d}(T)$
[/mm]
wegen der Monotonie der Funktion $f(x) [mm] =\bruch{2(x-1)}(x)$.
[/mm]
Induktiv folgt nun auch [mm] $\overline{d}(H') \le \overline{d}(T)$ [/mm] für alle Teilgraphen $H'$ von $T$, womit die Ausgewogenheit von $T$ gezeigt ist.
OK, ist doch was länger geworden. Schönen Gruß.
Andre
|
|
|
|
