\documentclass[12pt]{article}
\usepackage{german}
\usepackage{times}
\usepackage{din_a4}
%\usepackage{epsf}

%\usepackage{amsfonts}
\parindent=0pt
\parskip3mm



\begin{document}
 

%\vskip-2truecm


\section{ }

\section*{Graphen, Hypergraphen, Matroide: \\
wichtige Definitionen und Bezeichnungen}

Prof. Dr. Martin Gr\"otschel \hfill 3. Januar 2001

Bei der nachfolgenden Zusammenstellung von Begriffen und Bezeichnungen aus der Graphen-,
Hypergraphen- und Matroidtheorie handelt es sich nicht um eine didaktische Einf"uhrung in das Gebiet
der diskreten Mathematik. 
Dieses Kapitel ist lediglich als Nachschlagewerk gedacht, in dem die wichtigsten Begriffe und 
Bezeichnungen zusammengefa"st und definiert sind.

\subsection{Grundbegriffe der Graphentheorie}



 Die Terminologie und Notation in der 
Graphentheorie ist  leider sehr uneinheitlich. Wir wollen daher hier einen  
kleinen Katalog wichtiger graphentheoretischer Begriffe und Bezeichnungen 
zusammenstellen und zwar in der Form, wie sie (in der Regel) in meinen Vorlesungen benutzt werden. 
Definitionen werden durch Fettdruck hervorgehoben. Nach einer Definition folgen 
gelegentlich (in Klammern) weitere Bezeichnungen, um auf alternative 
Namensgebungen in der Literatur hinzuweisen.

 Es gibt sehr viele B\"ucher \"uber 
Graphentheorie. 
Wenn man zum Beispiel in der Datenbank MATH des Zentralblattes f"ur Mathematik nach B"uchern sucht, 
die den Begriff ``graph theory'' im Titel enthalten, erh"alt man fast 250 Verweise.
Bei rund 50 B"uchern taucht das Wort ``Graphentheorie'' im Titel auf.
Ich kenne nat"urlich nicht alle dieser B"ucher.
Zur Einf\"uhrung in die mathematische Theorie empfehle ich 
u.~a.~Aigner (1984), Bollob\'{a}s (1998), Diestel (2000), Bondy und Murty (1976) und West (2000).
 St\"arker 
algorithmisch orientiert und anwendungsbezogen sind z.~B.~Ebert (1981), 
Golombic (1980), Jungnickel (1994) und Walther und N\"agler (1987).


\subsection{Graphen}

Ein {\bf Graph} $G$ ist ein Tripel $(V,E,\Psi)$ bestehend aus einer
nicht-leeren Menge $V$, einer Menge $E$ und einer {\bf Inzidenzfunktion} 
$\Psi : E \rightarrow V^{(2)}$. Hierbei bezeichnet $V^{(2)}$ die Menge der 
ungeordneten Paare von (nicht notwendigerweise verschiedenen) Elementen von $V$. 
 Ein Element aus $V$ hei\ss t {\bf Knoten} (oder Ecke oder Punkt oder 
Knotenpunkt; englisch: vertex oder node oder point), ein Element aus $E$ hei\ss 
t {\bf Kante}
(englisch: edge oder line). Zu jeder Kante $e \in E$ gibt es also Knoten $u,v 
\in V$ mit $\Psi(e)=uv=vu$. (In der Literatur werden auch die  Symbole $[u,v]$ 
oder $\{ u,v \}$ zur Bezeichnung des ungeordneten Paares $uv$ benutzt.
Wir lassen zur Bezeichnungsvereinfachung die Klammern weg, es sei denn, dies f"uhrt
zu unklarer Notation. Zum Beispiel bezeichnen wir die Kante zwischen Knoten 1
und Knoten 23 nicht mit 123, wir schreiben dann $\{1,23\}$.)

Die Anzahl der Knoten eines Graphen hei\ss t {\bf Ordnung} des Graphen. Ein 
Graph hei\ss t {\bf endlich}, wenn $V$ und $E$ endliche Mengen sind, andernfalls
hei\ss t $G$ {\bf unendlich}. Wir werden uns nur mit endlichen Graphen 
besch\"aftigen und daher ab jetzt statt ``endlicher Graph'' einfach ``Graph'' 
schreiben. Wie werden versuchen, die nat\"urliche Zahl $n$ f\"ur die Knotenzahl 
und die nat\"urliche Zahl $m$ f\"ur die Kantenzahl eines Graphen zu reservieren. 
(Das gelingt wegen der geringen Anzahl der Buchstaben unseres Alphabets nicht immer.)

Gilt $\Psi (e) =uv$ f\"ur eine Kante $e \in E$, dann hei\ss en die Knoten $u,v 
\in V$ {\bf Endknoten} von $e$, und wir sagen, da{\ss} $u$ und $v$ mit $e$ {\bf 
inzidieren} oder {\bf auf} $e$ {\bf liegen}, da{\ss} $e$ die Knoten $u$ und $v$ 
{\bf verbindet}, und da{\ss} $u$ und $v$ {\bf Nachbarn} bzw. {\bf adjazent} 
sind. Wir sagen auch, da{\ss} zwei Kanten {\bf inzident} sind, wenn sie einen 
gemeinsamen Endknoten haben. Eine Kante $e$ mit $\Psi (e) =uu$ hei\ss t {\bf 
Schlinge}; Kanten $e,f$ mit $\Psi (e) =uv = \Psi (f)$ hei\ss en {\bf parallel}, 
man sagt in diesem Falle auch, da"s die Knoten $u$ und $v$ durch eine {\bf 
Mehrfachkante} verbunden sind. Graphen, die weder Mehrfachkanten noch Schlingen enthalten, 
hei\ss en {\bf einfach}. Der einfache Graph, der zu jedem in $G$ adjazenten 
Knotenpaar $u,v$ mit $u \neq v$ genau eine $u$ und $v$ verbindende Kante 
enth\"alt, hei\ss t der $G$ {\bf unterliegende einfache Graph}. Mit  {$\Gamma (v)$}  
bezeichnen wir die Menge der Nachbarn eines Knotens $v$. Falls $v$ in einer 
Schlinge enthalten ist, ist $v$ nat\"urlich mit sich selbst benachbart.  {$\Gamma (W)$} $:=  \bigcup_{v \in W} \Gamma(v)$ ist die Menge der Nachbarn von $W \subseteq 
V$. Ein Knoten ohne Nachbarn hei\ss t {\bf isoliert}.

Die Benutzung der Inzidenzfunktion $\Psi$ f\"uhrt zu einem relativ aufwendigen 
Formalimus. Wir wollen daher die Notation etwas vereinfachen. Dabei entstehen 
zwar im Falle von nicht-ein\-fa\-chen Graphen gelegentlich Mehrdeutigkeiten, die 
aber i.~a. auf offensichtliche Weise interpretiert werden k\"onnen. Statt $\Psi 
(e) = uv$ schreiben wir von nun an einfach $e = uv$ (oder \"aquivalent $e = vu)$ 
und meinen damit die Kante $e$ mit den Endknoten $u$ und $v$. Das ist korrekt, 
solange es nur eine Kante zwischen $u$ und $v$ gibt. Gibt es mehrere Kanten mit 
den Endknoten $u$ und $v$, und sprechen wir von der Kante $uv$, so soll das 
hei\ss en, da{\ss} wir einfach eine der parallelen Kanten ausw\"ahlen. Von jetzt 
an vergessen wir  also die Inzidenzfunktion $\Psi$ und benutzen die Abk\"urzung 
$G=(V,E)$, um einen Graphen zu bezeichnen. Manchmal schreiben wir auch $E_G$ 
oder $E(G)$ bzw. $V_G$ oder $V(G)$ zur Bezeichnung der Kanten- bzw. Knotenmenge 
eines Graphen $G$.


Zwei Graphen $G =(V,E$) und $H=(W,F)$ hei\ss en {\bf isomorph}, wenn es eine 
bijektive Abbildung $\varphi : V \rightarrow W$ gibt, so da{\ss} $uv \in E$ 
genau dann gilt, wenn $\varphi(u)\varphi(v) \in F$ gilt. Isomorphe Graphen sind 
also --- bis auf die Benamung der Knoten und Kanten --- identisch. 


Eine Menge $F$ von Kanten hei\ss t {\bf Schnitt}, wenn es eine Knotenmenge $W 
\subseteq V$ gibt, so da{\ss} $F = \delta (W) := \{uv \in E \mid u \in W ,v \in 
V \setminus W \}$ gilt; manchmal wird $\delta (W)$ der {\bf durch} $W$ {\bf 
induzierte Schnitt} genannt. Statt $\delta (\{v\})$ schreiben wir kurz 
$\delta(v)$. Ein Schnitt, der keinen anderen nicht-leeren Schnitt als echte 
Teilmenge enth\"alt, hei\ss t {\bf Cokreis}. Wollen wir betonen, da{\ss} ein 
Schnitt $\delta(W)$ bez\"uglich zweier Knoten $s,t \in V$ die Eigenschaft $s \in 
W$ und $t \in V \setminus W$  hat, so sagen wir, $\delta(W)$ ist ein 
  \mathversion{bold}{\bfseries $s$ und $t$ trennender Schnitt}\mathversion{normal}
oder kurz ein 
  \mathversion{bold}{\bfseries $[s,t]$-Schnitt}\mathversion{normal}. 



Generell benutzen wir die eckigen Klammern $[.\;,\;.]$, um anzudeuten, da\ss\ 
die Reihenfolge der Objekte in der Klammer ohne Bedeutung ist. Z.~B.~ist ein 
$[s,t]$-Schnitt nat\"urlich auch ein $[t,s]$-Schnitt, da ja $\delta (W) 
=\delta(V \setminus W)$ gilt. 

Wir haben oben Bezeichnungen wie $\Gamma (v)$ oder $\delta (W)$ eingef\"uhrt 
unter der stillschweigenden Voraussetzung, da\ss\ man wei\ss , bez\"uglich 
welches Graphen diese Mengen definiert sind. Sollten mehrere Graphen involviert 
sein, so werden wir, wenn Zweideutigkeiten auftreten k\"onnen, die Graphennamen 
als Indizes verwenden, also z.~B.~$\Gamma_G(v)$ oder $\delta_G(V)$ schreiben. 
Analog wird bei allen anderen Symbolen verfahren.

Der {\bf Grad} (oder die Valenz) eines  Knotens $v$ (Bezeichnung: $\mathbf{\deg(v)})$ ist die Anzahl der 
Kanten, mit denen er inzidiert, wobei Schlingen doppelt gez\"ahlt werden. Hat 
ein Graph keine Schlingen, so ist der Grad von $v$ gleich $| \delta (v) |$. Ein 
Graph hei\ss t $\mathbf{k}${\bf -regul\"ar}, wenn  jeder Knoten den Grad $k$ hat, oder 
kurz {\bf regul\"ar}, wenn der Grad $k$ nicht hervorgehoben werden soll. 

Sind $W$ eine Knotenmenge und $F$ eine Kantenmenge in $G =(V,E)$, dann 
bezeichnen wir mit $E(W)$ die Menge aller Kanten von $G$ mit beiden Endknoten in 
$W$ und mit $V(F)$ die Menge aller Knoten, die Endknoten mindestens einer Kante 
aus $F$ sind. 

Sind $G=(V,E)$ und $H =(W,F)$ zwei Graphen, so hei\ss t der Graph $(V \cup W, E 
\cup F)$ die {\bf Vereinigung} von $G$ und $H$, und $(V \cap W, E \cap F)$ 
hei\ss t der {\bf Durchschnitt} von $G$ und $H$. $G$ und $H$ hei\ss en {\bf 
disjunkt}, falls $V \cap W = \emptyset$, {\bf kantendisjunkt}, falls $E \cap F = 
\emptyset$. Wir sprechen von einer {\bf disjunkten} bzw. {\bf kantendisjunkten 
Vereinigung} von zwei Graphen, wenn sie disjunkt bzw. kantendisjunkt sind.


Sind $G =(V,E)$ und $H =(W,F)$ Graphen, so da\ss\ $W \subseteq V$ und $F 
\subseteq E$ gilt, so hei\ss t $H$ {\bf Untergraph} (oder Teilgraph) von $G$. 
Falls $W \subseteq V$, so bezeichnet $G - W$ den Graphen, den man durch {\bf 
Entfernen} (oder Subtrahieren) aller Knoten in $W$ und aller Kanten mit 
mindestens einem Endknoten in $W$ gewinnt. $G[W] :=G - (V \setminus W)$ hei\ss t 
der {\bf von} $W$ {\bf induzierte Untergraph} von $G$. Es gilt also $G[W] = 
(W,E(W))$. F\"ur $F \subseteq E$ ist $G - F :=(V,E \setminus F)$ der Graph, den 
man durch {\bf Entfernen} (oder Subtrahieren) der Kantenmenge $F$ enth\"alt. 
Statt $G - \{ f \}$ schreiben wir $G - f$, analog schreiben wir $G - w$ statt $G 
- \{w \}$ f\"ur $w \in V$. Ein Untergraph $H =(W,F)$ von $G =(V,E)$ hei\ss t 
{\bf aufspannend}, falls $V =W$ gilt.

Ist $G = (V,E)$ ein Graph und $W \subseteq V$ eine Knotenmenge, so bezeichnen 
wir mit $G \cdot W$ den Graphen, der durch {\bf Kontraktion der Knotenmenge} $W$ 
entsteht. Das hei\ss t, die Knotenmenge von $G \cdot W$ besteht aus den Knoten 
$V \setminus W$ und einem neuen Knoten $w$, der die Knotenmenge $W$ ersetzt. Die 
Kantenmenge von $G \cdot W$ enth\"alt alle Kanten von $G$, die mit keinem Knoten 
aus $W$ inzidieren, und alle Kanten, die genau einen Endknoten in $W$ haben, 
aber dieser Endknoten wird durch $w$ ersetzt (also k\"onnen viele parallele 
Kanten entstehen). Keine der Kanten von $G$, die in $E(W)$ liegen, geh\"ort zu 
$G \cdot W$. Falls $e =uv \in E$ und falls $G$ keine zu $e$ parallele Kante 
enth\"alt, dann ist der Graph, der durch {\bf Kontraktion der Kante} $e$ entsteht 
(Bezeichnung 
$G \cdot e$), der Graph $G \cdot \{ u,v \}$. Falls $G$ zu $e$ parallele Kanten 
enth\"alt, so erh\"alt man  $G \cdot e$ aus $G \cdot \{ u,v \}$ durch Addition 
von so vielen Schlingen, die den neuen Knoten $w$  enthalten, wie es Kanten in 
$G$ parallel zu $e$ gibt. Der Graph $G \cdot F$, den man durch {\bf Kontraktion} 
{\bf einer Kantenmenge} $F \subseteq E$ erh\"alt, ist der Graph, der durch 
sukzessive Kontraktion (in beliebiger Reihenfolge) der Kanten aus $F$ gewonnen 
wird. Ist $e$ eine Schlinge von $G$, so sind $G \cdot e$ und $G-e$ identisch.  

Ein einfacher Graph hei\ss t {\bf vollst\"andig}, wenn jedes Paar seiner Knoten 
durch eine Kante verbunden ist. Offenbar gibt es --- bis auf Isomorphie --- nur 
einen vollst\"andigen Graphen mit $n$ Knoten. Dieser wird mit $K_n$ bezeichnet. 
Ein Graph $G$, dessen Knotenmenge $V$ in zwei disjunkte nicht-leere Teilmengen 
$V_1, V_2$ mit $V_1 \cup V_2=V$ zerlegt werden kann, so da\ss\ keine zwei Knoten 
in $V_1$ und keine zwei Knoten in $V_2$ benachbart sind, hei\ss t {\bf bipartit} 
(oder paar). Die Knotenmengen $V_1, V_2$ nennt man eine {\bf Bipartition} (oder 
2-F\"arbung) von $G$. Falls $G$ zu je zwei Knoten $u \in V_1$ und $v \in V_2$ 
genau eine Kante $uv$ enth\"alt, so nennt man $G$ {\bf vollst\"andig bipartit}. 
Den --- bis auf Isomorphie eindeutig bestimmten --- vollst\"andig bipartiten 
Graphen mit $|V_1| = m, |V_2|=n$ bezeichnen wir mit $K_{m,n}$.


Ist $G$ ein Graph, dann ist das {\bf Komplement} von $G$, bezeichnet mit 
$\overline{G}$, der einfache Graph, der dieselbe Knotenmenge wie $G$ hat und 
bei dem zwei Knoten genau dann durch eine Kante verbunden sind, wenn sie in $G$ 
nicht benachbart sind. Ist $G$ einfach, so gilt ${\buildrel = \over G} = G$. Der 
{\bf Kantengraph} (englisch: line graph) $L(G)$ eines Graphen $G$ ist der 
einfache Graph, dessen Knotenmenge die Kantenmenge von $G$ ist und bei dem zwei 
Knoten genau dann adjazent sind, wenn die zugeh\"origen Kanten in $G$ einen 
gemeinsamen Endknoten haben. 

Eine {\bf Clique} in einem Graphen $G$ ist eine Knotenmenge $Q$, so da\ss\ je 
zwei Knoten aus $Q$ in $G$ benachbart sind. Eine {\bf stabile Menge} in einem 
Graphen $G$ ist eine Knotenmenge $S$, so da\ss\ je zwei Knoten aus $S$ in $G$ 
nicht benachbart sind. F\"ur stabile Mengen werden auch die Begriffe 
unabh\"angige Knotenmenge oder Coclique verwendet. Eine Knotenmenge $K$ in $G$ 
hei\ss t {\bf Knoten\"uberdeckung} (oder \"Uberdeckung von Kanten durch Knoten), 
wenn jede Kante aus $G$ mit mindestens einem Knoten in $K$ inzidiert. Die 
gr\"o\ss te Kardinalit\"at (= Anzahl der Elemente) einer stabilen Menge (bzw. 
Clique) in einem Graphen bezeichnet man mit $\mathbf{\alpha (G)}$ (bzw. $\mathbf{\omega(G)})$; die 
kleinste Kardinalit\"at einer Knoten\"uberdeckung mit $\mathbf{\tau(G)}$. 

Eine Kantenmenge $M$ in $G$ hei\ss t {\bf Matching} (oder Paarung oder 
Korrespondenz oder unabh\"angige Kantenmenge), wenn $M$ keine Schlingen 
enth\"alt und je zwei Kanten in $M$ keinen gemeinsamen Endknoten besitzen. $M$ 
hei\ss t {\bf perfekt}, wenn jeder Knoten von $G$ Endknoten einer Kante des 
Matchings $M$ ist. Ein perfektes Matching wird auch {\bf 1-Faktor} genannt. Eine 
Kantenmenge $F$ in $G$ hei\ss t $k${\bf -Faktor}, wenn jeder Knoten von $G$ in 
genau $k$ Kanten aus $F$ enthalten ist. Eine {\bf Kanten\"uberdeckung} (oder 
\"Uberdeckung von Knoten durch Kanten) ist eine Kantenmenge, so da\ss\ jeder 
Knoten aus $G$ mit mindestens einer Kante dieser Menge inzidiert. Die gr\"o\ss te 
Kardinalit\"at eines Matchings in $G$ bezeichnet man mit $\nu(G)$, die kleinste 
Kardinalit\"at einer Kanten\"uberdeckung mit  $\rho(G)$.

Eine  Zerlegung der Knotenmenge eines Graphen in stabile Mengen, die sogenannten 
{\bf Farbklassen}, hei\ss t {\bf Knotenf\"arbung}; d.~h.~die Knoten werden so 
gef\"arbt, da\ss\ je zwei benachbarte Knoten eine unterschiedliche Farbe haben. 
Eine Zerlegung der Kantenmenge in Matchings hei\ss t {\bf Kantenf\"arbung}; die 
Kanten werden also so gef\"arbt, da\ss\ je zwei inzidente Kanten verschieden 
gef\"arbt sind. Eine Zerlegung der Knotenmenge von $G$ in Cliquen hei\ss t {\bf 
Cliquen\"uberdeckung} von $G$. Die minimale Anzahl von stabilen Mengen (bzw. 
Cliquen) in einer Knotenf\"arbung (bzw. Cliquen\"uberdeckung) bezeichnet man mit 
$\mathbf{\chi(G)}$ (bzw. $\mathbf{\overline{\chi}(G)}$), die minimale Anzahl von Matchings in 
einer Kantenf\"arbung mit $\mathbf{\gamma(G)}$. Die Zahl $\gamma(G)$ hei\ss t {\bf 
chromatischer Index} (oder Kantenf\"arbungszahl), $\chi(G)$ {\bf F\"arbungszahl} 
(oder Knotenf\"arbungszahl oder chromatische Zahl).

Ein Graph $G =(V,E)$ kann in die Ebene gezeichnet werden, indem man jeden Knoten 
durch einen Punkt repr\"asentiert und jede Kante durch eine Kurve (oder Linie 
oder Streckenst\"uck), die die beiden Punkte verbindet, die die Endknoten der 
Kante repr\"asentieren. Ein Graph hei\ss t {\bf planar} (oder pl\"attbar), falls 
er in die Ebene gezeichnet werden kann, so da\ss\ sich keine zwei Kanten  (d.~h. 
die sie repr\"asentierenden Kurven) schneiden --- au\ss er m\"oglicherweise in 
ihren Endknoten. Eine solche Darstellung eines planaren Graphen $G$ in der Ebene 
nennt man auch {\bf Einbettung} von $G$ in die Ebene.

 

\subsection{Digraphen}

Die Kanten eines Graphen haben keine Orientierung. In vielen Anwendungen spielen
aber Richtungen eine Rolle. Zur Modellierung solcher Probleme f\"uhren wir 
gerichtete Graphen ein. Ein {\bf Digraph} (oder {\bf gerichteter Graph}) 
$D=(V,A)$ besteht aus einer (endlichen) nicht-leeren {\bf Knotenmenge} $V$ und 
einer (endlichen) Menge $A$ von {\bf B\"ogen} (oder gerichteten Kanten; 
englisch: arc). Eine {\bf Bogen} $a$ ist ein geordnetes Paar von Knoten, also 
$a=(u,v)$, $u$ ist der {\bf Anfangs-} oder {\bf Startknoten}, $v$ der {\bf End-} 
oder {\bf Zielknoten} von $a$; $u$ hei\ss t {\bf Vorg\"anger} von $v$, $v$ {\bf 
Nachfolger} von $u$, $a$ {\bf inzidiert mit} $u$ und $v$. (Um exakt zu sein, 
m\"u\ss ten wir hier ebenfalls eine Inzidenzfunktion $\Psi =(t,h) : A 
\rightarrow V \times V$ einf\"uhren. F\"ur einen Bogen $a \in A$ ist dann $t(a)$ 
der Anfangsknoten (englisch: tail) und $h(a)$ der Endknoten (englisch: head) von 
$a$. Aus den bereits oben genannten Gr\"unden wollen wir jedoch die 
Inzidenzfunktion nur in Ausnahmef\"allen benutzen.) Wie bei Graphen gibt es auch 
hier {\bf parallele B\"ogen} und {\bf Schlingen}. Die B\"ogen $(u,v)$ und 
$(v,u)$ hei\ss en {\bf antiparallel}.


In manchen Anwendungsf\"allen treten auch ``Graphen'' auf, die sowohl gerichtete 
als auch ungerichtete Kanten enthalten. Wir nennen solche Objekte {\bf gemischte 
Graphen} und bezeichnen einen gemischten Graphen mit $G=(V,E,A)$, wobei $V$ die 
Knotenmenge, $E$ die Kantenmenge und $A$ die Bogenmenge von $G$ bezeichnet.

Falls $D=(V,A)$ ein Digraph ist und $W \subseteq V, B \subseteq A$, dann 
bezeichnen wir mit $A(W)$ die Menge der B\"ogen, deren Anfangs- und Endknoten 
in $W$  liegen, und mit $V(B)$ die Menge der Knoten, die als Anfangs- oder 
Endknoten mindestens eines Bogens in $B$ auftreten. Unterdigraphen, induzierte 
Unterdigraphen, aufspannende Unterdigraphen, Vereinigung und Durchschnitt von 
Digraphen, das Entfernen von Bogen- oder Knotenmengen und die Kontraktion von 
Bogen- oder Knotenmengen sind genau wie bei Graphen definiert. 

Ist $D=(V,A)$ ein Digraph, dann hei\ss t der Graph $G=(V,E)$, der f\"ur jeden 
Bogen \mbox{$(i,j) \in A$} eine Kante $ij$ enth\"alt, der $D$ {\bf unterliegende 
Graph}. Analog werden der $D$ {\bf unterliegende einfache Graph} und der {\bf 
unterliegende einfache Digraph} definiert. Wir sagen, da\ss\ ein Digraph eine 
``ungerichtete'' Eigenschaft hat, wenn der ihm unterliegende Graph diese 
Eigenschaft hat (z.~B., $D$ ist bipartit oder planar, wenn der $D$ unterliegende 
Graph $G$ bipartit oder planar ist). Geben wir jeder Kante $ij$ eines Graphen  
$G$ eine Orientierung, d.~h., ersetzen   wir $ij$ durch einen der B\"ogen $(i,j)$ 
oder $(j,i)$, so nennen wir den so entstehenden Digraphen $D$ {\bf Orientierung} 
\mbox{von $G$.} 

Ein einfacher Digraph hei\ss t {\bf vollst\"andig}, wenn je zwei Knoten $u \neq 
v$ durch die beiden B\"ogen $(u,v), (v,u)$ verbunden sind. Ein {\bf Turnier} ist 
ein Digraph, der f\"ur je zwei Knoten \hbox{$u \neq v$} genau einen der B\"ogen 
$(u,v)$ oder $(v,u)$ enth\"alt. (Der einem Turnier unterliegende Graph ist also 
ein vollst\"andiger Graph; jedes Turnier ist die Orientierung eines 
vollst\"andigen Graphen.)

F\"ur $W \subseteq V$ sei $\delta^+ (W):= \{ (i,j) \in A |~ i \in W,j \not\in W 
\}, \delta^- (W) := \delta^+ (V \setminus W)$ und 
$\delta (W) := \delta^+ (W) \cup \delta^- (W)$. Die Bogenmenge $\delta^+ (W)$ 
(bzw. $\delta^- (W)$) hei\ss t {\bf Schnitt}. Ist $s \in W$ und $t \not\in W$, 
so hei\ss t $\delta^+ (W)$ auch $\mathbf{(s,t)}${\bf -Schnitt}. (Achtung: in einem 
Digraphen ist ein $(s,t)$-Schnitt kein $(t,s)$-Schnitt!) 
Statt $\delta^+ (\{ v \} ), \delta^- ( \{v \} ), \delta ( \{ v \} )$ schreiben 
wir  $\delta^+ (v), \delta^- (v), \delta (v)$, Der {\bf Au\ss engrad} ({\bf 
Innengrad}) von $v$ ist die Anzahl der B\"ogen mit Anfangsknoten (Endknoten) 
$v$. Die Summe von Au\ss engrad und Innengrad ist der {\bf Grad} von $v$. Ein 
Schnitt $\delta^+ (W), \emptyset \neq W \neq V$, hei\ss t {\bf gerichteter 
Schnitt}, falls $\delta^- (W)= \emptyset$, d.~h.~ falls $\delta(W) = \delta^+ 
(W)$. Ist $r \in W$, so sagen wir auch, da\ss\ $\delta^+(W)$ ein {\bf Schnitt 
mit Wurzel} $r$ ist. 



\subsection{Ketten, Wege, Kreise, B\"aume}

Das gr\"o\ss te Durcheinander in der graphentheoretischen Terminologie herrscht 
bei den Begriffen Kette, Weg, Kreis und bei den damit zusammenh\"angenden Namen. 
Wir haben uns f\"ur folgende Bezeichnungen entschieden. 

In einem Graphen oder Digraphen hei\ss t eine endliche Folge 
$W=(v_0,e_1,v_1,e_2,v_2, \cdots ,$
$e_k,v_k), \linebreak k \geq 0$, die mit einem Knoten beginnt und endet und in der Knoten 
und Kanten (B\"ogen) alternierend auftreten, so da\ss\ jede Kante (jeder Bogen) 
$e_i$ mit den beiden Knoten $v_{i-1}$ und $v_i$ inzidiert, eine {\bf Kette}. Der 
Knoten $v_0$
hei\ss t {\bf Anfangsknoten}, $v_k$ {\bf Endknoten} der Kette; die Knoten $v_1 , 
\ldots , v_{k-1}$ hei\ss en {\bf innere Knoten}; $W$ wird auch $[v_0,v_k]$-{\bf 
Kette} genannt. Die Zahl $k$ hei\ss t {\bf L\"ange} der Kette (= Anzahl der 
Kanten bzw. B\"ogen in $W$). Falls (in einem Digraphen) alle B\"ogen $e_i$ der 
Kette $W$ der Form $(v_{i-1},v_i)$ (also gleichgerichtet) sind, so nennt man $W$ 
{\bf gerichtete Kette}
bzw. ($v_0,v_k)${\bf -Kette}. Ist $W=(v_0,e_1,v_1, \ldots ,e_k,v_k)$ eine Kette, 
und sind $i,j$ Indizes mit $0 \leq i < j \leq k$, dann hei\ss t die Kette 
$(v_i,e_{i+1},v_{i+1}, \ldots ,e_j,v_j)$ das $[v_i,v_j]${\bf -Segment} (bzw. 
$(v_i,v_j)${\bf -Segment}, wenn $W$ gerichtet ist) von $W$. Jede (gerichtete) 
Kante, die zwei Knoten der Kette $W$ miteinander verbindet, die aber nicht 
Element von $W$ ist, hei\ss t {\bf Diagonale} (oder Sehne) von $W$. 


Gibt es in einem Graphen keine parallelen Kanten, so ist eine Kette $W$ bereits 
durch die Folge $(v_0,\ldots ,v_k)$ ihrer Knoten eindeutig festgelegt. 
Desgleichen ist in einem Digraphen ohne parallele B\"ogen eine gerichtete Kette 
durch die Knotenfolge $(v_0,\ldots,v_k)$ bestimmt. Zur Bezeichnungsvereinfachung 
werden wir daher h\"aufig von der Kette $(v_0,\ldots,v_k)$ in einem Graphen bzw. 
der gerichteten Kette $(v_0,\ldots,v_k)$  ein einem Digraphen sprechen, obgleich 
bei parallelen Kanten (B\"ogen) die benutzten Kanten (B\"ogen) hiermit nicht 
eindeutig festgelegt sind. Diese geringf\"ugige Ungenauigkeit sollte aber keine 
Schwierigkeiten bereiten. Gelegentlich interessiert man sich mehr f\"ur die 
Kanten (B\"ogen) einer Kette, insbesondere wenn diese ein Weg oder ein Kreis 
(siehe unten) ist. In solchen F\"allen
ist es zweckm\"a\ss iger, eine Kette als Kantenfolge $(e_1,e_2,\ldots,e_k)$ zu 
betrachten. Ist $C$ die Menge der Kanten (B\"ogen) eines Kreises oder eines 
Weges, so spricht man dann einfach vom Kreis oder Weg $C$, w\"ahrend $V(C)$ die 
Menge der Knoten des Kreises oder Weges bezeichnet. Je nach behandeltem 
Themenkreis wird hier die am besten geeignete Notation benutzt. 

Eine Kette, in der alle Knoten voneinander verschieden sind, hei\ss t {\bf Weg}. 
Eine Kette, in der alle Kanten oder B\"ogen verschieden sind, hei\ss t {\bf 
Pfad}. Ein Weg ist also ein Pfad, aber nicht jeder Pfad ist ein Weg. Ein Weg 
oder Pfad in  einem Digraphen, der eine gerichtete Kette ist, hei\ss t {\bf 
gerichteter Weg} oder {\bf gerichteter Pfad}. Wie bei Ketten sprechen wir von 
$\mathbf{[u,v]}${\bf -Wegen}, $\mathbf{(u,v)}${\bf -Wegen} etc.

 Im Englischen hei\ss t Kette walk oder chain. Im Deutschen benutzen 
z.~B.~Domschke (1982), H\"assig (1979) und Berge und Ghouila-Houri (1969) 
ebenfalls das Wort Kette, dagegen schreiben Aigner (1984), Diestel (1986) und Wagner (1970) 
hierf\"ur ``Kantenzug'', w\"ahrend K\"onig (1936), Halin (1989) und Sachs (1970) 
``Kantenfolge'' benutzen; Ebert (1981) schlie\ss lich nennt unsere Ketten 
``ungerichtete Pfade''. Dieses Wirrwarr setzt sich bez\"uglich der Begriffe Pfad 
und Weg auf \"ahnliche Weise fort.


Eine Kette hei\ss t {\bf geschlossen}, falls ihre L\"ange nicht Null ist und 
falls ihr An\-fangs\-kno\-ten mit ihrem Endknoten \"ubereinstimmt. Eine 
geschlossene (gerichtete) Kette, in der der An\-fangs\-kno\-ten und alle 
in\-ne\-ren Kno\-ten von\-ein\-an\-der ver\-schie\-den sind, hei\ss t {\bf 
Kreis} ({\bf gerichteter Kreis}). 
Offensichtlich enth"alt jede geschlossene Kette einen Kreis.

Eine (gerichtete) Kette, die jede Kante (jeden Bogen) eines Graphen (Digraphen) 
genau einmal enth\"alt, hei\ss t (gerichteter) {\bf Eulerpfad}. Ein 
geschlossener Eulerpfad hei\ss t {\bf Eulertour}. Ein {\bf Eulergraph} 
(Eulerdigraph) ist ein Graph (Digraph), der eine (gerichtete) Eulertour 
enth\"alt. 

Ein (gerichteter) Kreis (Weg) der L\"ange $|V|$ (bzw. $|V|-1$) hei\ss t 
(gerichteter) {\bf Hamiltonkreis} ({\bf Hamiltonweg}). Ein Graph (Digraph), der 
einen (gerichteten) 
Hamiltonkreis enth\"alt, hei\ss t {\bf hamiltonsch}. Manchmal sagen wir statt 
Hamiltonkreis einfach {\bf Tour}. 


Ein {\bf Wald} ist ein Graph, der keinen Kreis enth\"alt. Ein 
zusammenh\"angender Wald hei\ss t {\bf Baum}. Ein Baum in einem Graphen hei\ss t 
{\bf aufspannend}, wenn er alle Knoten des Graphen enth\"alt. 
Ein {\bf Branching} $B$ ist ein Digraph, der ein Wald ist, so da\ss\ jeder 
Knoten aus $B$ Zielknoten von h\"ochstens einem Bogen von $B$ ist. Ein 
zusammenh\"angendes Branching hei\ss t {\bf Arboreszenz}. 
Eine {\bf aufspannende Arboreszenz} ist eine Arboreszenz in einem Digraphen $D$,
die alle Knoten von $D$ enth\"alt.
Eine Arboreszenz enth\"alt einen besonderen Knoten, genannt {\bf Wurzel}, von 
dem aus jeder andere Knoten auf genau einem gerichteten Weg erreicht werden 
kann. Arboreszenzen werden auch {\bf Wurzelb\"aume} genannt. Ein Digraph, der 
keinen gerichteten Kreis enth\"alt, hei\ss t {\bf azyklisch}. 


Ein Graph hei\ss t {\bf zusammenh\"angend}, falls es zu jedem Paar von Knoten 
$s,t$ einen $[s,t]$-Weg in $G$ gibt. Ein Digraph $D$ hei\ss t {\bf stark 
zusammenh\"angend}, falls es zu je zwei Knoten $(s,t)$ von $D$ sowohl einen 
gerichteten $(s,t)$-Weg als auch einen gerichteten $(t,s)$-Weg in $D$ gibt. Die {\bf 
Komponenten} ({\bf starken Komponenten}) eines Graphen (Digraphen) sind die 
bez\"uglich Kanteninklusion (Bogeninklusion) maximalen zusammenh\"angenden 
Untergraphen von $G$ (maximalen stark zusammenh\"angenden Unterdigraphen von 
$D$). Eine Komponente hei\ss t {\bf ungerade Komponente}, falls ihre Knotenzahl 
ungerade ist, andernfalls hei\ss t sie {\bf gerade Komponente}.

Sei $G=(V,E)$ ein Graph. Eine Knotenmenge $W \subseteq V$ hei\ss t {\bf 
trennend}, falls $G-W$ unzusammenh\"angend ist. F\"ur Graphen $G =(V,E)$, die 
keinen vollst\"andigen Graphen der Ordnung $| V |$ enthalten, setzen wir 
$\kappa(G) := \min \{ | W | \mid W \subseteq V  ~\hbox{ ist trennend} \}$. Die 
Zahl  $\kappa(G)$ hei\ss t {\bf Zusammenhangszahl} (oder 
Knotenzusammenhangszahl) von $G$. F\"ur jeden Graphen $G=(V,E)$, der einen 
vollst\"andigen Graphen der Ordnung $|V|$ enth\"alt, setzen wir 
$\kappa (G) :=|V|-1$. Falls $\kappa (G) \geq k$, so nennen wir $G$ $k${\bf -fach 
knotenzusammenh\"angend} (kurz: {\bf $k$-zusammenh\"angend}. Ein wichtiger Satz 
der Graphentheorie (Satz von Menger) besagt, da\ss\ $G$ $k$-fach 
zusammenh\"angend genau dann ist, wenn jedes Paar $s,t,s \neq t$, von Knoten 
durch mindestens $k$ knotendisjunkte $[s,t]$-Wege miteinander verbunden ist. 
(Eine Menge von $[s,t]$-Wegen hei\ss t {\bf knotendisjunkt}, falls keine zwei 
Wege einen gemeinsamen inneren Knoten besitzen und die Menge der in den 
$[s,t]$-Wegen enthaltenen Kanten keine parallelen Kanten enth\"alt.)
 
Eine Kantenmenge $F$ eines Graphen $G=(V,E)$ hei\ss t {\bf trennend}, falls $G 
-F$ unzusammenh\"angend ist.  F\"ur Graphen $G$, die mehr als einen Knoten 
enthalten, setzen wir $\lambda (G):=\min \{ | F | \mid F \subseteq E ~~{\rm 
trennend} \}$. Die Zahl $\lambda (G)$ hei\ss t {\bf 
Kan\-ten\-zu\-sam\-men\-hangs\-zahl}. F\"ur Graphen  $G$ mit nur einem Knoten 
setzen wir $\lambda(G)=0$. Falls $\lambda(G) \geq k$, so nennen wir $G$ {\bf 
$k$-fach kantenzusammenh\"angend} (kurz: {\bf $k$-kantenzusammenh\"angend}). 
Eine Version des Menger'schen Satzes besagt, da\ss\ $G$ 
$k$-kantenzusammenh\"angend genau dann ist, wenn jedes Paar $s,t,s \neq t$, von 
Knoten durch mindestens $k$ kantendisjunkte $[s,t]$-Wege verbunden ist. F\"ur 
Graphen $G$ mit mindestens einem Knoten sind die Eigenschaften ``$G$ ist 
zusammenh\"angend'', ``$G$ ist 1-kantenzusammenh\"angend'' \"aquivalent. 

Analoge Konzepte kann man in Digraphen definieren. Man benutzt hierbei den 
Zusatz ``stark'', um den ``gerichteten Zusammenhang'' zu kennzeichnen. Wir 
sagen, da\ss\ ein Digraph $D=(V,A)$ {\bf stark $k$-zu\-sam\-men\-h\"angend} 
(bzw. {\bf stark} $k$-{\bf bo\-gen\-zu\-sam\-men\-h\"an\-gend}) ist, falls jedes 
Knotenpaar $s,t,s \neq t$ durch mindestens $k$ knotendisjunkte (bzw. 
bogendisjunkte) $(s,t)$-Wege verbunden ist. Wir setzen 
${\vec \kappa} (D):= \max \{ k \mid D$  ~stark~ $k$-zu\-sam\-men\-h\"an\-gend 
$\}$ und ${\vec \lambda} (D) := \max \{ k ~| ~ D \hbox{ stark 
$k$-bo\-gen\-zu\-sam\-men\-h\"angend} \}$; ${\vec \lambda} (D)$ hei\ss t die 
{\bf starke Zusammenhangszahl} von $D$, ${\vec \lambda} (D)$ die {\bf starke 
Bogenzusammenhangszahl} von $D$.

Ein Kante $e$ von $G$ hei\ss t {\bf Br\"ucke} (oder Isthmus), falls $G-e$ mehr 
Komponenten als $G$ hat. Ein Knoten $v$ von $G$ hei\ss t {\bf Trennungsknoten} 
(oder Artikulation), falls die Kantenmenge $E$ von $G$ so in zwei nicht-leere 
Teilmengen $E_1$ und $E_2$ zerlegt werden kann, da\ss\ $V(E_1) \cap V(E_2)=\{ 
v\}$ gilt. Ist $G$ schlingenlos mit $|V| \geq 2$, dann ist $v$ ein 
Trennungsknoten genau dann, wenn $\{ v\}$ eine trennende Knotenmenge ist, d.~h. 
wenn $G -v$ mehr Komponenten als $G$ besitzt. Ein zusammenh\"angender Graph ohne 
Trennungsknoten wird {\bf Block} genannt. Bl\"ocke sind entweder isolierte Knoten, Schlingen oder 
Graphen mit 2 Knoten, die durch eine Kante oder mehrere parallele Kanten 
verbunden sind oder, falls $|V| \geq 3,$ 2-zusammenh\"angende Graphen. Ein {\bf 
Block eines Graphen} ist ein Untergraph, der ein Block und maximal bez\"uglich 
dieser Eigenschaft ist. Jeder Graph ist offenbar die Vereinigung seiner 
Bl\"ocke. 



\subsection{Hypergraphen}

Sei $V$ eine endliche Menge und ${\cal E} = (E_i \mid i \in I)$ eine endliche 
Familie von Teilmengen von $V$. ${\cal E}$ hei\ss t endlicher {\bf Hypergraph }
 auf $V$, falls $E_i \neq \emptyset$ f\"ur alle $i \in I$ und $\bigcup_{i 
\in I} E_i =V$ gilt. Manchmal nennt man auch das Paar $(V,\cal E)$  {\bf Hypergraph}. $|V|$ ist 
die {\bf Ordnung} des Hypergraphen, die Elemente von $V$ hei\ss en {\bf Knoten}, 
die Mengen $E_i$ {\bf Hyperkanten} (oder kurz Kanten).   

Die Hyperkanten mit genau einem Element hei\ss en {\bf Schlingen}. Ein Hypergraph 
hei\ss t {\bf einfach}, wenn alle Kanten voneinander verschieden sind. In diesem 
Falle ist $\cal E$ eine Teilmenge von $2^V$. ($2^V$ bezeichnet die Potenzmenge 
von $V$.) 

Jeder Graph ohne isolierte Knoten kann also als Hypergraph aufgefa\ss t werden, 
dessen \mbox{(Hyper-)} Kanten h\"ochstens 2 Elemente enthalten. Ein einfacher Graph ohne 
isolierte Knoten ist ein einfacher Hypergraph mit $|E_i|=2$ f\"ur alle $i \in 
I$. 

Es ist gelegentlich n\"utzlich, graphentheoretische Objekte als Hypergraphen 
aufzufassen. Sei z.~B.~ $D=(V,A)$ ein Digraph, und seien $s,t \in V$ zwei 
festgew\"ahlte Knoten. Sei $B \subseteq A$ die Menge der B\"ogen, die auf 
mindestens einem $(s,t)$-Weg liegen. Seien ${\cal E}_1 := \{ P \subseteq B \mid 
P$ ist die Bogenmenge eines $(s,t) \hbox{-Weges } \}$, ${\cal E}_2 := \{ C 
\subseteq B \mid C$ ist ein $(s,t)\hbox{-Schnitt in } (V,B) \}$, dann sind 
$(B,{\cal E}_1)$ und $(B,{\cal E}_2)$ zwei interessante Hypergraphen, die uns in 
der Theorie der Blocker wiederbegegnen werden. In dieser Theorie sind besonders 
{\bf Antiketten} (oder Clutter) von Interesse. Das sind Hypergraphen $(V,\cal 
E)$, so da\ss\ f\"ur je zwei Kanten $E,F \in \cal E$ weder $E \subseteq F$ noch 
$F \subseteq E$ gilt. Der oben definierte Hypergraph $(B,{\cal E}_1)$ ist f\"ur 
jeden Digraphen $D$ eine Antikette, dies gilt jedoch nicht f\"ur den 
Hypergraphen $(B,{\cal E}_2)$. 


\subsection{Matroide, Unabh\"angigkeitssysteme}

Ist $E$ eine endliche Menge und ~${\cal I} \subseteq 2^E$ eine Menge von Teilmengen 
von $E$, dann hei\ss t ~${\cal I}$ oder das Paar $(E,{\cal I})$ {\bf 
Unabh\"angigkeitssystem}  auf $E$, falls gilt:

\hspace*{3mm}{(I.1)}\hspace*{3mm} $\emptyset \in {{\cal I}}$

\hspace*{3mm}{(I.2)}\hspace*{3mm} $I \subseteq J \in {\cal I} \Longrightarrow I \in {\cal I}.$

\noindent
 

Die Elemente von ~${\cal I}$~ hei\ss en {\bf un\-ab\-h\"an\-gi\-ge Mengen},
die Men\-gen in~$2^E \setminus {{\cal I}}$~    {\bf abh\"angige Mengen}.
$(E,{{\cal I}} \setminus \{ \emptyset \} )$ ist also ein einfacher Hypergraph.
Beispiele graphentheoretisch interessanter 
Un\-ab\-h\"an\-gig\-keits\-sys\-teme sind etwa die Menge aller Mat\-chings $\{ M 
\subseteq E \mid $ \hbox{$M$ Mat\-ching $\}$} oder die Menge aller stabilen 
Kno\-ten\-men\-gen 
$\{S \subseteq V \mid S \hbox{ stabil } \}$ eines Graphen $G=(V,E)$ oder 
die Men\-ge aller Bran\-chings $\{ B \subseteq A \mid (V,B) \hbox{ Branching } 
\}$ eines Digraphen $D=(V,A)$.

Ein Un\-ab\-h\"an\-gig\-keits\-sys\-tem $(E,{\cal I})$  hei\ss t 
{\bf Matroid}, falls gilt

\hspace*{3mm}{(I.3)}\hspace*{3mm} $I,J \in {\cal I}, |I|=|J|+ 1 \Longrightarrow \exists e \in I 
\setminus J \hbox{ mit } J \cup \{ e \} \in {\cal I}$.

\noindent
Ist $(E,{\cal I})$ ein Un\-ab\-h\"an\-gig\-keits\-sys\-tem und $F \subseteq E$, dann 
hei\ss t jede Menge $B \subseteq F$ mit $B \in {\cal I}$, die in keiner weiteren Menge 
mit diesen beiden Eigenschaften enthalten ist, {\bf Basis} von $F$. Die Zahl
$$r(F) := \max \{ |B| \mid B \hbox{ Basis von } F \}$$
\noindent
ist der {\bf Rang} von $F$ bez\"uglich $(E,{\cal I})$ . F\"ur Matroide $(E,{\cal I})$ 
folgt aus (I.3), da\ss\ f\"ur jede Menge $F \subseteq E$ alle Basen von $F$ die 
gleiche Kardinalit\"at besitzen. 

Eine abh\"angige Menge $C \subseteq E$, die die Eigenschaft hat, da\ss\ $C 
\setminus \{ e \}$ unabh\"angig ist f\"ur alle  $e \in C$, hei\ss t {\bf 
Zirkuit} (oder Kreis) des Unabh\"angigkeitssytems $(E,{\cal I})$.

Ein klassisches Beispiel f\"ur Matroide ist das folgende. Sei $G=(V,E)$ ein 
Graph. Dann ist ${\cal I} := \{ F \subseteq E \mid (V,F) \hbox{ Wald} \}$ das 
Unabh\"angigkeitssystem eines Matroids auf $E$. Dieses Matroid wird das {\bf 
graphische Matroid} bez\"uglich $G$ genannt. Die Zirkuits von $(E,{\cal I})$ sind 
die Kreise von $G$, die Basen einer Kantenmenge $F$ sind die Vereingungen von 
aufspannenden B\"aumen der Komponenten von $(V(F),F)$.

Ist $E$ eine Menge und ${\cal I} \subseteq 2^E$ ein 
Mengensystem, so nennen wir eine Menge $M \in {\cal I}$ 
{\bf maximal} (bzw. {\bf minimal}) bez\"uglich ${\cal I}$, wenn 
es keine Menge $M' \in {\cal I}$ gibt mit \hbox{$M \subset M'$} (bzw.  
$M' \subset M$). $M \in {\cal I}$ hei\ss t ein {\bf gr\"o\ss tes} 
(bzw. {\bf kleinstes}) Element von ${\cal I}$, wenn \hbox{$| M' \mid \leq 
\mid M |$} \hbox{( bzw. } $| M' \mid \geq | M |)$ gilt f\"ur alle $M' \in 
{\cal I}$. So sind z.~B. bez\"uglich eines 
Un\-ab\-h\"an\-gig\-keits\-sys\-tems  $(E, {\cal I})$ und einer Menge $F 
\subseteq E$ die Basen von $F$ genau die maximalen Elemente 
von ${\cal I}_F := \{ I \in {\cal I} \mid  I \subseteq F \}$. Nicht jede 
Basis ist auch ein gr\"o\ss tes Element von ${\cal I}_F$. (Z.~B. 
sind nicht alle maximalen Matchings (maximalen stabilen 
Knotenmengen) in einem Graphen gr\"o\ss te Matchings 
(gr\"o\ss te stabile Mengen).) Ist  $(E, {\cal I})$ jedoch ein 
Matroid, so sind alle maximalen Elemente von ${\cal I}_F$  auch 
gr\"o\ss te Elemente von  ${\cal I}_F$. (In einem 
zu\-sam\-men\-h\"an\-gen\-den Graphen sind z.~B.~alle maximalen 
W\"alder aufspannende B\"aume.)


Gute Einf\"uhrungen in die Matroidtheorie sind die B"ucher Oxley (1992) und   Welsh (1976).



\subsection{Liste einiger in der Graphentheorie verwendeter Symbole}
\begin{tabular}{ll}

  $G$          & bezeichnet meistens einen Graphen\\
 $D$          & bezeichnet meistens einen Digraphen\\
 $n$          & Anzahl der Knoten eines Graphen (wenn m\"oglich)\\
 $m$          & Anzahl der Kanten eines Graphen (wenn m\"oglich)\\
 $\alpha(G)$  & Stabilit\"atszahl = maximale Kardinalit\"at einer stabilen   
Menge in $G$ \\
 $\omega(G)$  & Cliquenzahl = maximale Kardinalit\"at einer Clique in $G$\\
 $\tau(G)$    & Knoten\"uberdeckungszahl =   minimale Kardinalit\"at\\
              &   einer Knoten\"uberdeckung von $G$\\
 $\rho(G)$    & Kanten\"uberdeckungszahl =   minimale Kardinalit\"at\\
             &     einer Kanten\"uberdeckung von $G$\\
 $\nu(G)$       &    Matchingzahl = maximale Kardinalit\"at eines 
Matchings in    $G$\\
 $\chi(G)$    & F\"arbungszahl =   chromatische Zahl = minimale Anzahl \\
                &   von stabilen Mengen in einer Knotenf\"arbung von $G$\\
 $\overline{\chi}(G)$  &   Cliquen\"uberdeckungszahl = minimale 
Anzahl von Cliquen\\
                &  in einer Cliquen\"uberdeckung von $G$ \\
 $\gamma(G)$  & Kantenf\"arbungszahl =   chromatischer Index = minimale Anzahl 
\\
                &   von Matchings in einer Kantenf\"arbung von $G$ \\
 $\Delta(G)$   &   maximaler Grad eines Knotens von $G$ \\    
 $\delta(G)$   & minimaler Grad eines Knotens von $G$ \\
 $\delta(W)$   & der durch die Knotenmenge $W$ induzierte Schnitt \\
 $\delta^+(W)$ & Menge aller B\"ogen mit Anfangsknoten in $W$ und Endknoten in 
$V \setminus W$ \\
 $\delta^-(W)$ & Menge aller B\"ogen mit Endknoten in $W$ und Anfangsknoten in 
$V \setminus W$ \\
 $\kappa(G)$   & Zusammenhangszahl =   maximales $\kappa$, so da\ss\  $G$ 
                  $\kappa$-zusammenh\"angend ist\\
 $\vec{\kappa}(D)$ &   starke Zusammenhangszahl =   maximales 
$\kappa$, so da\ss\ $G$ 
                  stark $\kappa$-zusammenh\"angend ist \\
 $\lambda(G)$  &   Kantenzusammenhangszahl =   maximales $\kappa$, so 
da\ss\  $G$ 
                   $\kappa$-kantenzusammenh\"angend ist\\
 $\vec\lambda(G)$ &   starke Bogenzusammenhangszahl =   maximales 
$\kappa$, so da\ss\  $D$ \\
              &    stark $\kappa$-bogenzusammenh\"angend ist\\
 $\Gamma(W)$   &   Menge der Nachbarn der Knotenmenge $W$ \\
 $G[W]$       & der von der Knotenmenge $W$ induzierte Untergraph von $G$ \\
 $G -W$       & der aus $G$ durch Entfernung der Knotenmenge $W$ entstehende 
Graph \\
 $G -F$       & der aus $G$ durch Entfernung der Kantenmenge $F$ entstehende 
Graph \\
 $G \cdot W$  & der aus $G$ durch Kontraktion der Knotenmenge $W$ entstehende 
Graph \\
 $G \cdot F$ & der aus $G$ durch Kontraktion der Kantenmenge $F$ entstehende 
Graph \\
 $\deg(v)$    & Grad des Knoten $v$ \\
 $E(W)$       & Menge aller Kanten von $G$ mit beiden Endknoten in $W$ \\
 $A(W)$       & Menge alle B\"ogen von $D$ mit Anfangs- und Endknoten in $W$ 
\\
 $V(F)$       & Menge aller Knoten aus $G$ (bzw.~ $D$) die Endknoten (bzw.~ 
Anfangs- oder\\
                & Endknoten) mit mindestens einer Kante (bzw.~eines Bogens) 
aus $F$ sind \\ 
 $K_n$        & vollst\"andiger Graph mit $n$ Knoten \\
$K_{m,n}$     & vollst\"andig bipartiter Graph mit $|V_1| = m \mbox{ und }|V_2|=n$ \\
 $L(G) $       & Kantengraph von $G$ \\
 $\overline{G}$ & Komplement von $G$ \\

\end{tabular}

\subsection{Literatur}

\medskip

\begin{description}
\item[] {M.~Aigner}
    {(1984)}
    {\sl Graphentheorie: Eine Entwicklung aus dem 4-Farben-Problem,}
    {Teubner Verlag, Stuttgart, 1984}

\item[]{B.~Bollob\'{a}s}
    {(1998)}
    {\sl Modern Graph Theory,}
    {Springer Verlag, New York, 1998}


\item[]{J.~A.~Bondy \& U.~S.~R.~Murty}
    {(1976)}
    {\sl Graph Theory with Applications,}
    {American Elsevier, New York and Macmillan, London, 1976}

\item[]{Berge und Ghouila-Houri}
    {(1969)}
    {\sl Programme, Spiele, Transportnetze,}
    {Teubner, Leipzig, 1969}

\item[]{R.~Diestel}
    {(2000)}
    {\sl Graphentheorie,}
    {Springer Verlag, Berlin, 2000, siehe auch URL: \\
{\tt www.math.uni-hamburg.de/home/diestel/books/graphentheorie}}


\item[]{W.~Domschke}
    {(1982)}
    {\sl Logistik: Rundreisen und Touren,}
    {Oldenbourg, M\"unchen, 1982}


\item[]{J.~Ebert}
    {(1981)}
    {\sl Effiziente Graphenalgorithmen,}
    {Wiesbaden, 1981}


\item[]{M.~C.~Golombic}
    {(1980)}
    {\sl Algorithmic Graph Theory and Perfect Graphs,}
    {Academic Press, New York, 1980}

\item[]R.~{Halin}
    {(1989)}
    {\sl Graphentheorie,}
    {Wissenschaftliche Buchgesellschaft, Darmstadt, 1989}


\item[]{K.~H\"assig}
    {(1979)}
    {\sl Graphentheoretische Methoden des Operations Research,}
    {Teubner, Stuttgart, 1979}
    
\item[]{D.~Jungnickel}
    {(1994)}
    {\sl Graphen, Netzwerke und Algorithmen,}
    {BI Wissenschaftsverlag,  Mann\-heim (3. Auflage)}


\item[]{D.~K\"onig}
    {(1936)}
    {\sl Theorie der endlichen und unendlichen Graphen,}
    {Akademische Verlagsgesellschaft, Leipzig, 1936 (mehrfach auf deutsch und in 
englischer \"Ubersetzung nachgedruckt)}

\item[]{J.~G.~Oxley}
    {(1992)}
    {\sl Matroid Theory,}
    {Oxford University Press, Oxford, 1992}


\item[]{H.~Sachs}
    {(1970)}
    {\sl Einf\"uhrung in die Theorie der endlichen Graphen,}
    {Teubner, Leipzig, 1970, und Hanser, M\"unchen, 1971}

\item[]{K.~Wagner}
    {(1970)}
    {\sl Graphentheorie,}
    {BI Wissenschaftsverlag, Mannheim, 1970}

\item[]{H.~Walther und G.~N\"agler}
    {(1987)}
    {\sl Graphen, Algorithmen, Programme, }
    {VEB Fachbuchverlag, Leipzig, 1987}


\item[]{D.~J.~A.~Welsh}
    {(1980)}
    {\sl Matroid Theory,}
    {Academic Press, New York, 1980}
    
 \item[]{D.~B.~West}
    {(2000)}
    {\sl Introduction to Graph Theory,}
    {Second Edition, Prentice Hall, Upper Saddle River, 2000}   
\end{description}

\end{document}
