§5: Baum–Graphen

Chr.Nelius: Graphentheorie (WS 2015/16)
14
§5 : Baum–Graphen
(5.1) DEF: a) Ein Baum (–Graph) ist ein zusammenhängender Graph, der keine Kreise besitzt.
b) Ein Graph, dessen Zusammenhangskomponenten Bäume sind, heißt ein Wald (–Graph) .
(5.2) BEM: a) Beispiel für einen Baum:
b) Beispiel für einen Wald:
c) Jeder Baum–Graph ist schlicht.
d) Jede Kante in einem Baum–Graphen mit mindestens zwei Ecken ist eine Brücke.
(5.3) SATZ: Ein Baum–Graph T mit n Ecken hat genau n − 1 Kanten.
(5.4) FOLG: Ist W ein Wald mit n Ecken und r Zusammenhangskomponenten, so hat W genau
n − r Kanten.
(5.5) SATZ: Sei T ein Graph mit n Ecken. Dann sind folgende Aussagen (paarweise) äquivalent:
a) T ist ein Baum–Graph
b) T hat genau n − 1 Kanten und besitzt keinen Kreis
c) T hat genau n − 1 Kanten und ist zusammenhängend
d) T ist zusammenhängend, und jede Kante ist eine Brücke.
15
Chr. Nelius: Graphentheorie (WS 2015/16)
(5.6) SATZ: T sei ein Baum–Graph mit |E(T )| ≥ 2 . Dann enthält T (mindestens) zwei Ecken
vom Grade 1 .
(5.7) FOLG: T sei ein Baum–Graph mit mindestens zwei Ecken. Dann gilt:
δ(T ) = 1 .
(5.8) DEF: Sei G ein zusammenhängender Graph. Ein aufspannender Untergraph von G , der
ein Baum ist, heißt ein aufspannender Baum von G .
(5.9) SATZ: Sei G ein zusammenhängender Graph mit n Ecken und m Kanten. Dann besitzt G
einen aufspannenden Baum, der durch Entfernen von
ζ(G) = m − n + 1 .
Kanten von G entsteht. Die Anzahl ζ(G) der entfernten Kanten heißt der Zyklenrang von G .
(ζ (lies: zeta): kleines griechisches z)

Download Report