TU Wien:Mathematik 1 VO (Panholzer)/Stoff WS05/15. VO 16.11.2005

Graphentheorie

gerichtete oder ungerichtete Graphen: Darunter versteht man ein Tripel

$G=\langle V,E,f\rangle$

• V = V(G) ... Kontenmenge von G
• E = E(G) ,,, Kantenengen von G
• f ... Inzidenzabbildung

$f:E\rightarrow V^{2}$ (gr. Graphen)

$f:E\rightarrow \{\{v,w\}:v,w\in V\}$

f(e) = (a,b) ... a ist der Anfangsknoten, b der Endknoten

oder f(e) = {a,b}

$G=\langle V,E,f\rangle$

V = {a,b,c,d}, E = {$e_{1},e_{2},e_{3},e_{4},e_{5}$}

$f:E\rightarrow V^{2}$

$f(e_{1})=(a,a)$

$f(e_{2})=(a,b)$

$f(e_{3})=f(e_{4})=(b,c)$

$f(e_{5})=(c,b)$

Digraph ... gerichteter Graph

schlichter Graph

• keine Schlinge
• keine Mehrfachkanten

$\Rightarrow$ Graph kann angegeben werden als

$G=\langle V,E\rangle$

gerichteter Graph: $E\subseteq V^{2}$

ungerichteter Graph: $E\subseteq \{\{v,w\}:v,w\in V$

endliche Graphen, schlichte Graphen: $G=\langle V,E\rangle$

$V=\{v_{1},...,v_{n}\}\qquad E=\{e_{1},...,e_{n}\}$

|V| = n = $\alpha _{0}(G)$

$|E|=m=\alpha _{1}(G)$

Kante e auf $a\rightarrow b$ ist inzident mit den Konen a und b. Knoten a und b sind adjazent.

Schlichte endliche Graphen G können mit Hilfe der Adjazenzmatrix A(G) dargestellt werden

A ... $n\times m$ - Matrix. Der Eintrag $a_{ij}$, d.h. das Element in der i-ten Zeile und j-ten Spalte ist definiert als

(Bedingungsausdruck auf $a_{ij}$

  1 ... falls $v_{i}$ und $v_{j}$ adjazent sind

  0 .... 

$G=\langle V,E\rangle$

V = {a,b,c,d,e}

E = {ab,bc,bd,cd}

(Graph)

(Matrix)

Graph $G=\langle V,E\rangle$ (ungerichteter Graph)

Der Knotenpunkt d(v) ist gegeben als die Anzahl der mit v adjazenten Knoten (= Anzahl der Kanten, die durch v gehen),

$d(v_{i})=\sum _{j=1}^{n}a_{ij}=\sum _{j=1}^{n}a_{ji}$

• gerichteter Graph: Der Weg-Grad $d^{+}(v)$ ist die Anzahl der von v wegführenden Kanten (out-degree).

$d^{+}(v_{i})=\sum _{j=1}^{n}a_{ij}$ (i-tes Zeichen)

Der Hin-Grad $d^{-}(v)$ ist die Anzahl der zu v hinführenden Knoten (in-degree).

$d^{-}(v)=\sum _{j=1}^{n}a_{ij}$ (i-te Spalte)

  d(a) = 1
  d(b) = 3
  d(c) = 2
  d(d) = 2
  d(e) = 0

d(a) + d(b) + d(c) + d(d) + d(e) = 8 = 2*4 = 2 * |E|

allgemeine Regel Handschlaglemma:

In einem ungerichteten Graphen:

$\sum _{v\in V(G)}d(v)=2*|E(G)|$

In einem gerichteten Graphen $G=\langle V,E\rangle$

$\sum _{v\in V(G)}d^{+}(v)=\sum _{v\in V(G)}d^{+}-(v)=|E(G)|$

Beweis: vollständige Induktion nach |E(G)|

Idee:

• gerichtete Kante $v\rightarrow w$
• ungerichtete Kante $v---w$

Anmerkung: gilt für allgemeine Graphen (nicht schlichte)

wie zählt man Schlingen?

Schlinge $d^{+}(v)=d^{-}(v)=1$

Ungerichteter Graph: d(v) = 2

Beispiel: vollst. Graph

ungerichteter, schlichter Graph, wo 2 verschiedene Knoten durch eine Kante verbunden sind

$K_{n}$ ... vollst. Graph mit n Knoten

(Graphen)

$K_{n}...|V|=n$

|E| = ${\frac {n(n-1}{2}}$

$d(v)=d(v_{i})=n-1$

$\sum _{v\in V}d(v)=\sum _{v\in V}(n-1)=*(n-1)=2*|E(G)|$