TU Wien:Mathematik 1 VO (Panholzer)/Stoff WS05/17. VO 21.11.2005

S. unger. zusammenh. Graphen $G=\langle V,E\rangle$

alle Knotengrade gerade $\Leftrightarrow$ G. bes. geschlossene Eulersche Linie

(Graph 1)

Annahme; d(v)=0, $\forall v\in V$

da $G=\langle V,E\rangle$ zusammenhägend, $\Rightarrow$ |V| = 1 : Knoten ist $\in L$

sonst: d(v) > 0 $\neq$ d(v) $\geq 2\qquad \forall v\in V$

(aufgrund von G zusammenhängend und d(G) gerade)

Behauptung: dann gibt es einen geschlossenen Kantenzug

$d(v)\geq 2\qquad \forall v\in V$

(Graph 2)

$\Rightarrow$ es gibt einen Kreis $C_{1}$

betrachten Graphen $G_{1}=\langle V,E\backslash G\rangle$

$G_{1}$ i.A. nicht mehr zusammenhängend, aber es gilt: d(v) gerade ${\text{ }}\forall v\in V$

falls d(v) = 0 $\forall v\in V{\text{ in }}G_{1}$ ... dann fertig,

falls $\exists v\in V:d(v)>0\Rightarrow d(v)\geq 2$

Iteriere Verf.: Knotenring $\Rightarrow$ Kreis $C_{2}$

$\Rightarrow$ Graph $G_{2}=\langle E,C_{1}\backslash C_{2}\rangle$

liefert Menge von kantendipunkten Kreisen $C_{1},C_{2},...,C_{r}$ (jede Kante liegt in genau einem Kreis)

$\Rightarrow$ durch geeignetes Zusammensetzen der Kreise $C_{1},...,C_{r}$ bekommt man eine geschlossene Eulersche Linie

(Skriptum S. 30, Kreise/Bsp. K5)

Betr.: schlichte, ungerichtete Graphen offene Eulersche Linie $\Leftrightarrow$ es gibt genau zwei Konten mit unger. Grad

Betr.: gerichtete Graphen, stark zusammenhängend - Bedingung: $d^{+}(v)=d^{-}(v)\forall v\in V\qquad \Leftrightarrow$ G eulersch

Bäume,Wälder

Definition: Ein gerichteter Graph, der keine Kreise enthält, heißt Wald.

Ist er überdies zusammenhängend, nennt man ihn Baum.

(Graphen Skriptum S. 30)

Satz: Ein Graph G ist ein Baum, genau dann wenn je 2 verschiedene Knoten v,w durch genau einen Weg verbunden sind.

$\Rightarrow$ G ist ein Baum

angenommen, es gibt 2 verschiedene Wege von v nach w

(Graph 3 + Mitschrift dazu - wird nachgetragen)