Das Königsberger Brückenproblem
schlichter Graph: G=(E(G), K(G))
Ecke (Knoten, Punkt): E(G): Endliche Menge
Kante (Strecke): K(G): Endliche Menge ungeordneter Paare aus E(G)
Die Kante {v,w} verbindet die Ecken v und w.
Eine Schlinge ist eine Kante, die eine Ecke mit sich selber verbindet.
Ein Graph mit Schlingen und Mehrfachkanten heißt Allgemeiner Graph.
Ein Digraph (gerichteter Graph) D ist ein Paar (E(D), B(D)), wobei E(D) eine endliche nichtleere Menge ist (Ecken) und B(D) eine Menge geordneter Paare aus E(D), Bögen genannt.
Zwei Ecken v,w eines Graphen heißen benachbart, wenn v und w durch eine Kante {v,w} verbunden werden. v und w heißen inzident mit dieser Kante. Der Grad (Valenz) einer Ecke v ist die Zahl der mit v inzidenten Kanten. Eine Ecke vom Grad 0 heißt isolierte Ecke oder Endecke.
Handschlaglemma: Die Summe aller Grade aller Ecken ist gerade.
Zwei Graphen G1, G2 sind isomorph, wenn es eine umkehrbar eindeutige Abbildung von G1 nach G2 gibt.
Ein Teilgraph von G ist ein Graph, dessen Ecken zu E(G) und dessen Kanten zu K(G) gehören.
Nullgraph:
Vollständiger Graph Kn:
Paare (Bipartite) Graphen Km,n:
eine Kantenfolge ist eine endliche Folge {v0,v1},{v1,v2},...,{vm-1,vm}. Wir nennen v0 die Startecke, vm die Zielecke. Die Anzahl der Kanten einer Kantenfolge ist ihre Länge. Eine Kantenfolge, in der alle Kanten verschieden sind, heißt Linie. Sind die Ecken v0, v1,...,vm verschieden, so heißt sie Weg. Eine Linie oder ein Weg heißt geschlossen, falls v0=vm. Ein geschlossener Weg mit mindestend einer Kante heißt Kreis.
Ein Graph G heißt zusammenhängend, falls es zu je zwei Ecken v,w einen Weg von v nach w gibt. Jeder Graph kann in disjunkte, zusammenhängende Teilgraphen zerlegt werden, die man seine (Zusammenhangs-) Komponenten nennt. Ein Graph mit mehr als einer Komponente heißt unzusammenähngend.
Eine trennende Kantenmenge eines zusammenhängenden Graphen ist eine Menge von Kanten von G, nach deren Entfernung ein unzusammenhängender Graph übrigbleibt.
Ein Schnitt ist eine trennende Kantenmenge, die keine trennende kantenmenge als Teilmenge enthält. Ein Schnitt, der aus einer Kante besteht, ist eine Brücke.
[Untersuchungsgegenstand eulersche und hamiltonsche Graphen.]
Ein Wald ist ein Graph, der keine Kreise enthält. EIn zusammenhängender Wald heißt Baum.
Satz: Sei B ein Graph mit n Ecken. Dann sind folgende Aussagen äquivalent:
(i) B ist ein Baum
(ii) B enthält keine Kreise und hat n-1 Kanten
(iii) B ist zusammenhängend und hat n-1 Kanten
(iv) B ist zusammenhängend und jede Kante ist ein Brücke
(v) je zwei Ecken von B sind durch genau einen Weg miteinander verbunden
(vi) T enthält keine Kreise, aber das Hinzufügen irgendeiner Kante erzeugt genau einen Kreis.
[Untersuchung planare Graphen]
[Untersuchung Färbbarkeit]
Definition s.o.
ersetzt man jeden Bogen der Form (v,w) durch eine Kante der Form {v,w}, so erhält man den zugrundeliegenden Graphen
benachbart, inzident, isomorph, Bogenfolge, gerichtete Linie (Dilinie), gerichteter Weg (Diweg), gerichteter Kreis (Dikreis)
Ein Digraph D heißt (schwach) zusammenhängend, wenn er nicht als Vereinigung zweier disjunkter Graphen ausgedrückt werden kann. D.h. wenn der zugrundeliegende Graph zusammenhängend ist.
Gibt es zu zwei Ecken v und w von D einen gerichteten Weg zwischen v und w, so heißt D stark zusammenhängend.
Gesucht werden in einem Graphen G die maximale Anzahl von Wegen von v nach w, die keine Kante gemeinsam haben. Diese Wege heißen kantendisjunkt.
Eine v und w trennende Kantenmenge von G ist eine Menge E von Kanten aus G, mit der Eigenschaft, daß jeder Weg von v nach w mindestens eine Kante aus E enthält.
Satz von Menger: Die Maximalzahl kantendisjunkter Wege, die zwei voneinander verschiedene Ecken v und w in einem zusammenhängenden Graphen G verbinden, ist gleich der minimalen Anzahl von Kanten in einer v und w trennenden Kantenmenge
Auslastungssatz: Die maximale Anzahl der bogendisjunkten Diwege, die in einem Digraphen von einer Ecke v zu einer von v verschiedenen Ecke w führen, ist gleich der minimalen Anzahl von Bögen in einer v und w trennenden Bogenmenge.
Ein Netzwerk ist ein Digraph, bei dem jeder Bogen mit einer nichtnegativen, reellen Zahl k(a) versehen ist, die als dessen Kapazität bezeichnet wird. Ein Netzwerk hat die Form (D,k), wobei D ein Digraph ist und k eine Abbildung von B(D)->R+.
Der Ausgangsgrad k->(x) einer Ecke x ist die Summe aller Kapazitäten aller Bögen der Form (x,z), entsprechend wird der Eingangsgrad k<-(x) definiert.
Handschlags-Di-Lemma: Die Summe aller Ausgangsgrade aller Ecken ist gleich die Summe aller Eingangsgrade.
Ein Quelle hat den Eingangsgrad 0, eine Senke den Ausgangsgrad 0.
Im folgenden sei vorausgesetzt, daß der Digraph D genau eine Quelle und eine Senke hat.
Sei ein Netzwerk N=(D,k) gegeben. Ein Strom in N ist ein eine Funktion f, die jedem Bogen in D eine nichtnegative Zahl f(a) (Fluß in a) zuordnet daß (i) für jedem Bogen a in N gilt: f(a)<=k(a); (ii) in Bezug auf das Netzwerk (D,k) der Eingangsgrad jeder Ecke gleich ihrem Ausgangsgrad ist (ausgenommen v und w). Ist f(a)=u(a), so heißt a gesättigt, die übrigen Bögen heißen ungesättigt.
Aus dem Handschlags-Di-Lemma folgt, daß die Summe der Flüsse in den mit v inzidenten Kanten gleich die Summe der Flüsse der mit w inzidenten Kanten ist. DIese Summe heißt Stromstärke.
Wir suchen maximale Ströme.
Ein Schnitt ist eine Menge S von Bögen von D mit der Eigenschaft, daß jeder Diweg von v nach w wenigstens einen Bogen aus S enthält. Ein Schnitt ist eine v und w trennende Bogenmenge. Die Kapazität eines Schnittes S ist die Summe der Kapazitäten der Bögen in S. Schnitte mit minimaler Kapazität heißen minimale Schnitte. Im obigen Beispiel ist (v,z), (x,z), (y,z), (x,w) ein minimaler Schnitt der Kapazität sechs.
Satz von Ford-Fulkerson (max flow = min cut): In jedem Netzwerk ist die Stärke des maximalen Stroms gleich der Kapazität jedes minimalen Schnittes.
Klar ist, daß in einem Netzwerk nur soviel fließen kann, wie an der dünnsten Stelle hindurchpaßt. Der Satz sagt aber, daß auch nicht weniger fließt.
Ein nichtkonstruktiver Beweis des Satzes folgt aus dem Satz von Menger. Ein Beweis unter Angabe eines Maximalstroms liefert der Algorithmus von Ford-Fulkerson.
