next up previous contents
Next: Traversierung von Graphen Previous: Minimale Spannbäume

Grundlagen

Ein Graph G=(V,E) besteht aus einer Menge von Knoten V und einer Menge Kanten E. Die Anzahl der Knoten bezeichnen wir mit n (|V|=n), die Anzahl der Kanten mit m (|E|=m). Eine Kante $(v,v)\in E$ heißt Schlinge . Falls E eine Multimenge ist, spricht man von Mehrfachkanten . Kanten (u,v) und (v,u) heißen antiparallel . Graphen ohne Schlingen und Mehrfachkanten bezeichnen wir mit einfachen Graphen (eng. simple). Formal definiert:

\begin{displaymath} E \subseteq \left(\begin{array} {c} V\\ 2\\ \end{array} \right) =: \{X \subseteq V, \vert X\vert=2 \}\end{displaymath}

In diesem Fall bezeichnet man G=(V,E) als einen ungerichteten Graphen.

Graphische Darstellung:


\begin{picture} (140,62) \put(25,3){\circle*{2.5}} \put(55,23){\circle*{2.5}}... ...} \put(108,57){\makebox(0,0){Vollst''andiger bipartit, $K_{3,3}$}}\end{picture}


Ist $E\subseteq V \times V$, dann heißt G gerichteter Graph , für $(u,v)\in E:\\ $
\begin{picture} (34,10) \put(5,7){\circle*2{2}} \put(5,7){\circle*{2}} \put... ...24}} \put(5,3){\makebox(0,0){$u$}} \put(30,3){\makebox(0,0){$v$}}\end{picture}

Der zu G gehörige ungerichtete Graph ist G'=(V,E'). E' erhält man, indem man in E die Richtungen wegläßt und Mehrfachkanten beseitigt. Sei $v\in V$, unter der Nachbarschaft $N(v):=\{w;(v,w)\in E\}$ eines Knotens v versteht man die Menge der direkten Nachbarn von v. Der Grad eines Knotens ist definiert als:

$deg(v)= \left\{ \begin{array} {ll} \vert N(v)\vert & \text{; falls $G$\space un... ...} \\ indeg(v)+outdeg(v) & \text{; falls G gerichtet.}\\ \end{array} \right. $
Dabei sind indeg(v) die Anzahl aller Kanten, die v als Endknoten haben, und outdeg(v) die Anzahl aller Kanten, die v als Startknoten haben.
\fbox {Beobachtung: $\sum_{v\in V}deg(v)=2\vert E\vert$}

\fbox {\parbox[c]{12.45cm}{\textbf{Korollar:} In jedem Graphen ist die Anzahl der Knoten mit ungeradem Grad eine gerade Zahl. }}


Das Komplement $\overline{G}=(V,\left(\begin{array} {c} V\\ 2\\ \end{array} \right)-E)$ eines Graphen G=(V,E) besitzt die gleiche Knotenmenge V und hat als Kantenmenge alle Kanten des vollständigen Graphen ohne die Kantenmenge E.
Ein Graph H=(V',E') heißt Teilgraph (aka. Subgraph, Untergraph, ...) von G=(V,E), falls $V' \subseteq V$ und $E' \subseteq E$. H heißt (knoten-) induzierter Teilgraph, falls H Teilgraph von G ist, und es gilt $E'=E\cap \left(\begin{array} {c} V'\\ 2\\ \end{array} \right)$.

Ein Kantenzug ist eine Folge $e_1:=\{v_0,v_1\},\cdots,e_l:=\{v_{l-1},v_l\}$, wobei alle ei verschieden sind. v0 und vl bezeichnen wir als Endknoten. Die Länge des Kantenzuges bezeichnen wir mit l. Sind bei einem Kantenzug auch alle vi verschieden, so sprechen wir von einem Pfad. Ein Kantenzug mit vl=v0 heißt Zykel . Ein Zykel, in dem alle vi verschieden sind, heißt Kreis .
Ein Graph G heißt zusammenhängend , wenn es für alle $u,v\in V$ einen Pfad gibt, der u und v verbindet. Ein (kanten-) maximaler zusammenhängender Teilgraph heißt (Zusammenhangs-)Komponente .


\begin{picture} (170,47) \put(20,20){\circle*{2.5}} \put(50,10){\circle*{2.5}... ...ut(75,39){\makebox(0,0){$K_3$}} \put(117,42){\makebox(0,0){$K_4$}}\end{picture}


Ein Graph G ist azyklisch , wenn er keine Kreise enthält. Wir bezeichnen diesen dann als Wald . Ist dieser auch zusammenhängend, so sprechen wir von einem Baum . Ist der Teilgraph $T=(V,E)\subseteq G=(V,E)$ ein Baum, dann heißt T ein Spannbaum .

\fbox {\parbox[c]{12.45cm}{\textbf{Satz:} Ist $T=(V,E)$\space ein Baum, dann ist $\vert E\vert=\vert V\vert-1$. }}

Beweis: Induktion über die Anzahl der Knoten:
n=0,1 : klar.
$n \rightarrow n+1$ : Sei $v\in V$, $\vert V\vert=n+1,\ V'=V-\{v\},\ deg(v)=1$.
Solche Knoten müssen existieren, denn ansonsten würde ein Zykel entstehen, und das wäre ein Widerspruch zur Definition eines Baumes. $\Diamond$


\fbox {\parbox[c]{12.45cm}{\noindent\textbf{Korollar:} Ein Graph $G$\space ist zusammenh\uml {a}ngend, g.d.w. $G$\space ein Spannbaum hat. }}



  • Minimale Spannbäume