TU Wien:Mathematik 1 VO (Panholzer)/Stoff WS05/16. VO 17.11.2005

Def. $G=\langle V,E\rangle$

$G_{1}=\langle V_{1},E_{1}\rangle$ mit $V_{1}\subseteq V,E_{1}\subseteq E$ dann heißt $G_{1}$ Teilgraph von G

Definition betreffend gerichteten od. ungerichteten Graphen $G=\langle V,E\rangle$

Eine Folge

$x_{0},(x_{0},x_{1}),x_{1},(x_{1},x_{2}),x_{2},....,x_{k-1},(x_{k-1},x_{k}),x_{k}$

$x_{i}\in V,(x_{i},x_{i+1}(\in E$

heißt

• Kantenfolgen der Länge k
• eine offene Kantenfolge falls $x_{0}\neq x_{k}$, geschlossene falls $x_{0}=x_{k}$
• Ein Kantenring, falls alle Kanten paarweise verschieden sind
• ein Weg (Bahn = gerichteter Weg) falls alle Knoten und alle Kanten verschieden sind
• ein Kreis (Zyklus), falls alle Kanten und Knoten verschieden sind, bis auf $x_{0}=x_{k}$

(Beispiel mit Graph)

geschlossene KF aba kein Kreis!

es gilt: jede offene KF von v nach w kann zu einem Weg von v nach w reduziert werden

(Graph)

Beispiel: a c e d f e g d f e b

  a c e d f e g d f e b

Kursiv kann gestrichen werden

weiters gilt: jede geschlossene KZ kann zu einem Kreis reduziert werden

(Bsp. geschlossene KF)

Definition: Ein ungerichteter Graph heißt zusammenhängend, wenn zwischen je 2 Knoten v und w ($v,w\in V$) in G ein Weg existiert.

• Ein gerichteter Graph heißt stark zusammenhängend, wenn für je 2 Knoten v und w ein gerichteter Weg von v nach w und von w nach w existiert.
• schwach zusammenhängend, wenn der Schatten von G (bezeichnet als $G_{u}$ ) zusammenhängend ist.

(Der Schatten entsteht aus G durch Weglassen der Kantenorientierungen.)

Beispiel (Graph)

Definition: Betrachte gerichtete oder ungerichtete Graphen $G=\langle V,E\rangle$, zusammenhängend.

Eine Kantenfolge in der jede Kante von E genau einmal auftritt, heißt Eulersche Linie.

• Ein Weg in dem alle Knoten von V genau einmal auftreten, heißt Hamiltonsche Linie.

(Bei geschlossener Hamiltonscher Line, Ausnahme: AP = EP)

(Beispiel)

Satz: Ein ungerichteter, zusammenhängender Graph besitzt genau dann eine geschlossene Eulersche Linie, falls alle Knotengrade d(v) gerade sind.

Geschlossene Eulersche Linie $\Rightarrow d(v)$ gerade ( $\forall v\in V)$

(Graph)

$d(v)\neq 0$ (da stark zusammenhängend)