\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}