Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 
Autor: Dennis Kerzig

1. Das Haus vom Nikolaus

Das Haus vom Nikolaus als Graph \(N = (V,E)\) mit \(V=\{a,b,c,d,e\}\).
Sicher hat jeder von euch schon einmal versucht das Haus vom Nikolaus auf einem Blatt Papier zu zeichnen. Natürlich ohne zwischendurch abzusetzen oder eine Kante mehrfach zu zeichnen. Doch funktioniert das, egal bei welcher Ecke man anfängt? Und wieso geht das plötzlich nicht mehr, wenn der Nikolaus sein Haus um einen Anbau erweitert? Zur Formalisierung und Lösungsfindung solcher und vieler weiterer Probleme — wie beispielsweise der Routenplanung, Landkartenfärbung und Flussoptimierung — bietet sich ein Teilgebiet der Mathematik besonders an: die Graphentheorie.

Im folgenden führen wir den Grundbegriff eines Graphen ein und nennen wichtige Eigenschaften und Operationen. Ein Graph \(G\) ist ein Tupel aus der Menge seiner Knoten \(V(G)\) und der Menge seiner Kanten \(E(G)\): \(G=(V,E)\) benennen kann. Die Kanten ungerichteter Graphen setzen sich aus 2-elementigen, verschiedenen Teilmengen der \(v \in V\) zusammen. Bei uns steht \(n\) für die Anzahl aller Knoten \(|V|\) und \(m\) analog dazu für die Anzahl aller Kanten \(|E|\). Enthält \(E\) alle \(n(n-1) / 2\) möglichen Teilmengen, nennt man \(G\) einen vollständigen Graphen \(K^n\). Zwei Knoten \(v_1\) und \(v_2\) nennt man benachbart bzw. adjazent, wenn für die verbindene Kante \(\{v_1,v_2\} \in E\) gilt. Die Knoten \(v_1\) und \(v_2\) nennt man dann ebenfalls inzident zur Kante \(\{v_1,v_2\}\).

Die Anzahl aller inzidenten Kanten eines Knotens \(v\) nennt man den Knotengrad bzw. \(d_G(v)\). Der maximale Knotengrad \(\Delta(G)\) bezeichnet den Knotengrad eines Knotens mit den meisten inzidenten Kanten. Analog ist der minimale Knotengrad als \(\delta(G)\) definiert.

Wähle einen Teilgraphen, um die Veränderungen zum obigen Ausgangsgraphen \(T\) zu sehen.
Im Kontext eines Graphen \(G\) werden herkömmliche Mengenoperationen, wie sie z. B. bei den Mengen \(V\) oder \(E\) Anwendung finden, erweitert und abgekürzt. Anstatt explizit der Knotenmengen eines Graphen einen entsprechenden Knoten hinzuzufügen, schreibt man auch \(G \cup \{v\}\) oder \(G+v\). Entnimmt man einen Knoten, also \(G' = G - v\), so enthält \(G'\) gleichzeitig keine der zu \(v\) inzidenten Kanten. Die Notation zum Hinzufügen und Entfernen von Kanten ist analog. Entfernt man jedoch die letzte zu einem bestimmten Knoten inzidente Kante, so bleibt der Knoten trotzdem Teil des Graphen. Man nennt solche Knoten isoliert.

Existiert zu einem Graphen \(H = (V_H, E_H)\) ein Graph \(H' = (V_{H'}, E_{H'})\), so dass \(V_{H'} \subseteq V_H\) und \(E_{H'} = \{e\in E_H \text{ : } e \cap V_{H'} = e \}\) gelten, dann nennt man \(H'\) den durch \(V_{H'}\) induzierten Teilgraphen von \(H\). Dafür schreibt man auch \(H' = H[V_{H'}]\). Allgemeiner bezeichnet man \(H'\) als Teilgraphen von \(H\), wenn \(V_{H'} \subseteq V_H\) und \(E_{H'} \subseteq E_H\) gilt.

{
}
{
}
{
}
{
}
Die Anzahl der Ecken ungeraden Grades in einem Graphen \(G = (V,E)\) ist gerade.
Hinweise
Konstruiere die Mengen aller ungeraden und geraden Knoten und addiere ihre Knotengrade.
Beispiellösung
Wir partitionieren die Knotenmenge \(V\) in \(V_1 = \{v \in V \text{ : } d_G(v) \text{ gerade}\}\) und \(V_2 = \{v \in V \text{ : } d_G(v) \text{ ungerade}\}\), welche respektive die Menge aller Knoten geraden und ungeraden Grades darstellen. Zählt man die Knotengrade aller Knoten zusammen, so umfasst diese Zahl jede Kante genau zweimal, nämlich für jeden inzidenten Knoten: \(\sum\limits_{v\in V} d_G(v) = 2|E|\). Es folgt also \(\sum\limits_{v\in V_1} d_G(v) + \sum\limits_{v\in V_2} d_G(v) = 2|E|\). Der erste Summand muss gerade sein, weil er die Summe gerader Knotengrade darstellt. Da \(2|E|\) ebenfalls gerade ist, folgt, dass der zweite Summand auch gerade ist. Da eine Summe ungerader Zahlen nur bei einer geraden Anzahl von Sumanden gerade ist, folgt die Aussage.

2. Pfade und Kreise

Wähle einen Kreis/Pfad, um ihn im obigen Graphen \(I\) hervorzuheben.

Ein Weg oder auch Pfad von \(v_1\) nach \(v_k\) bezeichnet einen nichtleeren Graphen \(P^k=(V_P,E_P)\) mit \(V_P = \{v_1,v_2,...,v_k\}\) (wobei \(v_i \neq v_j\) für alle \(i\) und \(j\)) und \(E_P=\{\{v_1,v_2\},\{v_2,v_3\},...,\{v_{k-1},v_k\}\}\). Abkürzend bezeichnet man so einen Kantenzug \(P=v_1v_2...v_k\). Ausgehend von dieser Definiton nennt man \(P^k\) einen A-B-Weg genau dann, wenn \(V_P\cap A = \{v_1\}\) und \(V_P\cap B = \{v_k\}\) gilt. Analog dazu ist ein a-b-Weg ein A-B-Weg mit \(A=\{a\}\) und \(B=\{b\}\).

Der Abstand zweier Knoten \(v_1\) und \(v_2\) in \(G\) bzw. \(d_G(v_1,v_2)\) ist definiert als die geringste Länge eines \(v_1\)-\(v_2\)-Weges. Den größtmöglichen Abstand zweier Knoten nennt man den Durchmesser von \(G\) oder \(\mathrm{diam}(G)\). Außerdem nennt man einen Knoten \(v\) zentral, wenn sein Abstand zum entferntesten Knoten minimal ist.

Als Kreis \(C^k\) bezeichnet man formal \(C^k = P^{k-1} + \{v_{k-1}, v_1\}\), wobei der Weg \(P^k\) gleichzeitig als Knotenfolge \(v_1,...,v_{k-1}\) und auch als Graph \(P^{k-1}=(\{v_1,v_2,...,v_{k-1}\}, \{\{v_1,v_2\},...,\{v_{k-2},v_{k-1}\}\})\) betrachtet werden kann. Erweitert man diesen um die Kante \(\{v_{k-1}, v_1\}\), entsteht ein geschlossener Weg der Länge \(k > 2\): ein Kreis eben. Enthält ein Graph keinen Kreis, so nennt man ihn kreisfrei.

Erfüllt ein Weg die besondere Eigenschaft alle Knoten des zugehörigen Graphen genau einmal zu enthalten, so nennt man ihn einen Hamiltonweg. Ist der Weg zusätzlich geschlossen, existiert also eine Kante zwischen Anfangs- und Endknoten, dann ist der entsprechende Hamiltonweg gleichzeitig ein Hamiltonkreis. Transformiert man diese Überlegungen auf unser anfängliches Problem, dem Haus vom Nikolaus, dann sucht man einen Weg der nicht alle Knoten, sondern alle Kanten des Graphen \(N\) genau einmal besucht: einen Eulerweg. Analog zum Hamiltonkreis ist der Eulerkreis definiert.

{
}
Entwickle einen Algorithmus, der für einen gegebenen Graphen \(G\) und zwei verschiedene Knoten a und b entscheidet, ob ein a-b-Weg in \(G\) existiert. Beweise zudem die Korrektheit deines Algorithmus und gib die Laufzeit in der O-Notation an. Die Datenstruktur des Graphen kannst du dir frei überlegen (siehe z. B Adjazenzliste, Adjazenzmatrix).
Hinweise
Traversiere den Graphen vollständig und merke dir, welche Knoten du bereits besucht hast. Nutze zum Traversieren einen Stack oder eine Queue.
Beispiellösung

Ich nehme an, der Algorithmus bekommt den Graphen als Knotenarray übergeben, welches pro Knoten sowohl die Methode neighbours() implementiert, um alle Nachbarknoten zu ermitteln, sowie ich die Instanzvariable visited vom Typ Boolean enthält, die im Initialzustand false ist und angibt, ob ich den jeweiligen Knoten bereits besucht habe.

// Stapel initialisieren und Anfangsknoten drauflegen
Stack s = new Stack();
s.push(a);
a.visited = true;

while !s.isEmpty() {
    Node v = s.pop();

    // Durchlaufe alle noch nicht besuchten Nachbarn von v
    for Node n in v.neighbours() {
        if n.visited == false {
            n.visited = true;
            s.push(n);

            // Ist der Knoten der Zielknoten, so existiert ein Pfad
            if n == b { return true; }
        }
    }
}

// Alle erreichbaren Knoten wurden durchlaufen ohne 'b' zu finden.
return false;

Korrektheit des Algorithmus

Dass der Zielknoten b genau dann auf dem Stack liegt, wenn er von a aus erreichbar ist, zeige ich in zwei Richtungen. \((\rightarrow )\) Ich nehme an, der Knoten b liegt auf dem Stack s. Da gefordert ist, dass Ziel- und Anfangsknoten unterschiedlich sind, muss er also in der for-Schleife auf den Stack gelegt worden sein, die über alle unbesuchten Nachbarn eines anderen Knotens \(v\) iteriert. Da für \(v\) das gleiche Argument gilt, existiert eine Kette aus Nachbarn bis zum Startknoten a, der Eingabegraph enthält also ein a-b-Weg. \((\leftarrow )\) Aus der Annahme, dass ein a-b-Weg existiert folgt, dass es eine Kette von Nachbarn existiert, über die b von a aus erreichbar ist. Da Knoten bloß als besucht markiert werden, wenn sie bereits einmal auf dem Stack waren, muss also jeder dieser Nachbarn der Kette einmal auf dem Stack gelegen haben. Das gilt auch für den direkten Nachbarn von b (wovon er mindestens einen haben muss, weil ein Weg zu ihm existiert), weswegen folgt, dass auch b einmal auf dem Stack liegt.
Direkt nachdem der Zielknoten auf den Stack gelegt wurde, wird festgestellt, dass er der gesuchte Knoten ist und ein Weg existiert.

Terminierung des Algorithmus

Die einzige Stelle, an der der Algorithmus in eine Endlosschleife fallen könnte, ist in der while-Schleife, die solange läuft bis der Stack leer ist. Jeder Knoten des Eingabegraphen liegt höchstens einmal auf dem Stack, weil er beim Drauflegen gleichzeitig als besucht markiert wird und Knoten, die als besucht markiert wurden, später nicht mehr betrachtet werden. Da unser Eingabegraph zusätzlich logischerweise endlich ist, folgt, dass die Schleife bloß endlich viele Durchläufe macht.

Laufzeit des Algorithmus

Im Worstcase sind alle Knoten des Graphen zusammenhängend und der Zielknoten wird erst erreicht, wenn bereits alle anderen Knoten auf dem Stack waren. Da bis zu diesem Punkt für jeden Knoten des Graphen alle Nachbarn durchlaufen wurden, egal ob sie bereits besucht wurden oder nicht, entspricht die Laufzeit pro Knoten \(v\) genau \(\mathcal O(d_G(v))\). Weil jeder Knoten des Graphen genau einmal auf dem Stack landet, ergibt sich folgende Gesamtlaufzeit von \(\mathcal O(n+2m) = \mathcal O(n+m)\).


3. Zusammenhang

Der Graph \(Z\) besitzt drei Komponenten: \(Z[\{a,b,c\}]\), \(Z[\{d,e\}]\) und \(Z[\{f\}]\)
Eine wichtige Eigenschaft von Graphen ist der Zusammenhang. Man nennt einen Graphen zusammenhängend, wenn für alle Knoten paarweise ein a-b-Weg existiert. Einen maximal zusammenhängenden Teilgraphen bezeichnet man als Komponente des jeweiligen Graphen. Ein zusammenhängender Graph, wie z. B. der Nikolaus-Graph \(N\), besitzt genau eine Komponente.

Man nennt einen Graphen \(G\) genau dann \(k\)-zusammenhängend, wenn es eine Knotenmenge mit Mächtigkeit \(\geq k\) gibt, deren Entfernen zu einem unzusammenhängenden oder leeren Graphen führt, wohingegen das Entfernen einer beliebigen Knotenmenge mit Mächtigkeit \(< k\) den Graphen nicht zerfallen lässt. Jeder \(k\)-zusammenhängende Graph ist also gleichzeitig \((k-1)\)-, \((k-2)\)-, ... und \(0\)-zusammenhängend. Der Zusammenhang \(\kappa(G)\) steht für das größte \(k\), für das \(G\) \(k\)-zusammenhängend ist. Analog dazu ist der Kantenzusammenhang \(\lambda(G)\) und die Eigenschaft eines Graphen \(l\)-kantenzusammenhängend zu sein definiert. Achtung: Die Definition von \(k\)-Zusammenhang ist in der Literatur nicht einheitlich.

Ist ein Graph \(G = (V,E)\) zusammenhängend, so existiert für jedes \(k<n\) eine Aufzählung seiner Knoten \((v_1, ..., v_k)\), so dass \(G[\{v_1,...v_k\}]\) zusammenhängend ist.
Hinweise
Wähle ein beliebiges \(v_1\) und versuche nun mit einer bestimmten Reihenfolge über die Knoten zu traversieren (vgl. Algorithmusaufgabe, Abschnitt 2). Du kannst auch einen Algorithmus entwerfen, der das Problem löst und ihn beweisen (Terminierung, Korrektheit).
Beispiellösung

Ich werde die Aussage zeigen, indem ich einen Algorithmus angebe, der für einen zusammenhängenden Graphen als Eingabe die gesuchte Aufzählung liefert. Dann zeige ich seine Korrektheit und Terminierung. Der Eingabegraph G ist eine Menge aller Knoten, die jeweils über die Instanzmethode neighbours() die Menge aller adjazenten Knoten liefert.

// Geordnete Liste initialisieren und beliebigen Startknoten drauflegen
List l = new List();
l.append(G[0]);

while |l| < |G| {
    // Menge aller zu l[0],...,l[|l|-1] adjazenten Knoten ohne l
    Set newNeighbours = new Set();

    for Node n in l {
        newNeighbours += (n.neighbours() - l);
    }

    l.append(newNeighbours[0])
}

return l;

Korrektheit
Für meinen Beweis wähle ich die geforderte Eigenschaft der Aufzählung als Schleifeninvariante für die äußere while-Schleife, nämlich \(G[l] \text{ zusammenhängend}\). Weil ich in jedem Schleifendurchlauf genau einen Knoten hinzufüge, treffe ich damit jedes \(k \leq n\). Zur Initialisierung, also vor dem ersten Schleifendurchlauf, trifft die Invariante zu, da ein Graph mit nur einem Knoten immer zusammenhängend ist. Angenommen, die Aussage stimmt im \(n\)-ten Durchlauf. Ich zeige nun, dass daraus folgt, dass die Aussage im \((n+1)\)-ten Durchlauf auch stimmt. Nach Ende der inneren for-Schleife ist jeder Knoten \(v_i\) der Menge newNeighbours mit mindestens einem Knoten aus l adjazent, weil (wegen Annahme) der induzierte Teilgraph \(G[l]\) zusammenhängend ist, muss deswegen auch \(G[l+v_0]\) zusammenhängend sein.
Terminierung
Da der Eingabegraph zusammenhängend ist, wächst l solange um genau einen Knoten pro Iteration, bis alle Knoten aus G enthalten sind. Das sieht man leicht an der Kontraposition.
Entwickle zwei Algorithmen, die für einen gegebenen Graphen \(G\) entscheiden, ob er zusammenhängend ist. Nutze für die erste Variante den Algorithmus der Aufgabe von Abschnitt 2, nennen wir ihn z. B. existiertWeg(a,b,Graph), der true liefert, wenn ein a-b-Weg im Eingabegraphen existiert, sonst false. Die zweite Variante soll den Algorithmus der Beispiellösung aus Abschnitt 2 modifizieren.

Gib für beide Varianten eine Laufzeit in O-Notation an. Korrektheits- und Terminierungsbeweise brauchst du dieses Mal nicht zu machen.
Hinweise
Für Variante 1: Implementiere die exakte Definition von Zusammenhang.
Für Variante 2: Nutze die visited-Instanzvariable eines jeden Knotens. Wähle einen beliebigen Startpunkt für die Traversierung.
Beispiellösung
Variante 1

Der Eingabegraph G ist genau dann zusammenhängend, wenn für alle seine Knoten \(a,b\) ein \(a\)-\(b\)-Weg existiert. Man durchläuft also alle \(\binom{n}{2}\) Knotenpaare und ruft existiertWeg(a,b,Graph) auf, was jeweils \(\mathcal O(n+m)\) dauert.

forall pairs of Nodes (a, b) in G {
    if !existiertWeg(a,b,G) { return false; }
} 
return true;        
Daraus ergibt sich eine ernüchternde Gesamtlaufzeit von \(\mathcal O(n*(n-1)/2*(n+m)) = \mathcal O(n^3+mn^2)\).
Variante 2

Wir nehmen den Algorithmus aus der Aufgabe von Abschnitt 2 und entfernen die Überprüfung auf einen gewissen Zielknoten. Wir lassen die Tiefensuche solange arbeiten, bis sie alle erreichbaren Knoten besucht hat. Existiert dann trotzdem noch ein unbesuchter Knoten in G, so muss er in einer anderen Zusammenhangskomponenten liegen.

// Stapel initialisieren und beliebigen Anfangsknoten drauflegen
Stack s = new Stack();
s.push(G[0]);
a.visited = true;

while !s.isEmpty() {
    Node v = s.pop();

    // Lege alle noch nicht besuchten Nachbarn auf den Stapel
    for Node n in v.neighbours() {
        if n.visited == false {
            n.visited = true;
            s.push(n);
        }
    }
}

// Sollte ein Knoten noch nicht besucht sein, dann liegt er in einer anderen Komponente
for Node n in G {
    if !n.visited { return false; }
}

return true;
Die Laufzeit ist der aus Variante 1 deutlich überlegen, sie beträgt trotz der zusätzlichen Überprüfung des Besuchs aller Knoten noch \(\mathcal O(n+m)\).

4. Spezialformen: Bäume und partite Graphen

In vielen Anwendungsbereichen erfüllen Graphen, nachdem sie modelliert wurden, spezielle Eigenschaften. Oder man sucht Teilgraphen, die spezielle Eigenschaften erfüllen. Mindestens einen solchen Spezialfall haben wir bereits kennengelernt, nämlich den zusammenhängenden Graphen, in dem jeder Knoten von jedem anderen aus erreichbar ist. Diese Eigenschaft ist in der Routenplanung besonders wünschenswert und kann global (siehe Google-Maps) zum Beispiel durch die Integration von Fähren- und Luftrouten zwischen den Kontinenten und Inselgruppen der Welt sichergestellt werden. Im folgenden führen wir zwei andere praxisrelevante Sonderformen ein: Bäume und partite Graphen.

Der maximal kreisfreie Graph \(B\): ein Baum.
Bäume
Einen Graphen, der gleichzeitig zusammenhängend und kreisfrei ist, bezeichnet man als Baum. Allgemeiner nennt man einen Graphen, dessen Komponenten alle Bäume sind, einen Wald. Alle Knoten eines Baumes mit nur einer inzidenten Kante nennt man Blätter. Satz 0.5.1 aus Diestels Graphentheorie offenbart uns die wichtigsten Äquivalenzen eines Baums:

Die folgenden Aussagen sind äquivalent für einen Graphen \(G\):
  1. \(G\) ist ein Baum
  2. Für je zwei Knoten \(a,b\) enthält \(G\) genau einen \(a\)-\(b\)-Weg.
  3. \(G\) ist minimal zusammenhängend.
  4. \(G\) ist maximal kreisfrei.

Viele Graph-Algorithmen (z. B. Wegfindung oder Ermittlung eines zentralen Knotens) lassen sich auf Bäumen noch effizienter implementieren. Oft ist das Ziel auch, einen Teilgraphen eines (nichtkreisfreien) Eingabegraphen \(G\) zu finden, so dass er die Eigenschaften eines Baumes erfüllt und gleichzeitig alle Knoten von \(G\) enthält. Man nennt einen solchen speziellen Teilgraphen Spannbaum.
Verschiedene Darstellungen partiter Graphen. Die einzelnen Partitionen sind farblich hervorgehoben.
Partite Graphen

Bildet man einen Graphen \(R\) aus einer Menge von Arbeitern (Knoten), Aufgaben (Knoten) und Aufgabenpräferenzen der Arbeiter (Kanten), dann wird deutlich, dass \(R\) in zwei Partitionen zerfällt, deren Knoten untereinander keine Kanten teilen: die der Aufgaben und der Arbeiter. Graphen, die vollständig in \(k\) solcher Partitionen zerfallen, nennt man \(k\)-partit. Unser Graph \(R\) ist also 2-partit oder bipartit. Vollständige \(k\)-partite Graphen bezeichnet man auch mit \(K_{n_1,...,n_k}\), wobei \(n_i\) die Anzahl der Knoten der \(i\)-ten Partiton angibt.
Gesucht ist nun eine maximale Menge knotendisjunkter Kanten, also eine optimale Aufgabenzuordnung. Diese Problemstellung hat in vielen Gebieten große Relevanz, man bezeichnet sie als Matching oder Paarung.

Schon die bipartiten Graphen eröffnen ein weites Forschungsfeld. Zum Beispiel geht es um die algorithmischen Fragestellungen: Wie kann ein solches Matching gefunden werden? Existiert ein perfektes Matching? Ist ein gegebener Graph bipartit?

Beweise die folgenden Sätze:

  1. Jeder Baum \(T = (V,E)\) mit \(|V| \geq 2\) enthält mindestens zwei Blätter.
  2. Jeder Baum \(P\) hat mindestens so viele Blätter wie \(\Delta(P)\).
Hinweise
Wähle für beide Sätze entweder eine Startkante oder einen Starknoten, traversiere den Graphen und nutze eine Baumeigenschaft.
Beispiellösung
  1. Sei \(\{v,u\} \in E\) eine beliebige Kante. Nun traversieren wir so lange in Richtung von \(v\) und nach \(u\), bis wir bei einem Blatt ankommen. Dabei ist es egal, wo lang wir genau gehen, da \(T\) keine Kreise enthält und wir eine Kante bzw. einen Knoten deswegen nur höchstens einmal besuchen. \(T\) ist außerdem endlich, weshalb wir irgendwann in beiden Richtungen in einer Sackgasse, also einem Blatt, terminieren.

  2. In \(P\) existiert mindestens ein Knoten \(v\) mit \(d_G(v)=\Delta(P)\). Beginnend bei \(v\) traversieren wir den Graphen wie in 1. in alle \(\Delta(P)\) Richtungen.


5. Erweiterungen: Gerichtete Graphen und Kantengewichte

Unser Modell eines Graphen scheint zwar bereits äußerst vielseitig, stößt bei vielen Problemmodellierung jedoch schnell an seine Grenzen. Für die meisten Praxisanwendungen ist es nötig, die Kanten eines Graphen zu richten, also nur in eine Richtung begehbar zu machen. Um einen Weg dem anderen gegenüber zu präferieren, muss neben der Anzahl der Kanten auch eine spezielle Kantenwichtung verfügbar sein. Beide Modelle stellen wir nun kurz als Ausblick vor.

Gerichtete Graphen
Der gerichtete, kreisfreie Graph (DAG) \(D\).
Betrachtet man zum Beispiel zwei Orte \(a, b\) (die in einem Graphen als Knoten dargestellt sind), welche durch genau eine Einbahnstraße verbunden sind, dann wäre es nicht sinnvoll, diese Kante als ungerichtete Menge \(\{a,b\}\) zu abstrahieren. Eine gerichtete Kante hingegen ist als geordnetes Tupel \((a,b)\) definiert. Graphen können entweder nur ungerichtete oder gerichtete Kanten enthalten, man nennt sie dann respektive ungerichtet oder gerichtet.

Alle der besprochenen Termini lassen sich intuitiv für gerichtete Graphen formulieren, zum Beispiel kommt jedem Knoten \(v\) nun ein gesonderter Ausgangs- und Eingangsgrad für die Anzahl ausgehender Kanten \(d^+_G(v)\) bzw. die der eingehenden \(d^-_G(v)\) zu. Ein gerichter Weg \(P^k=v_1v_2...v_k\) nichts anderes als ein nicht-leerer Graph mit Knotenmenge \(\{v_1,v_2,...,v_k\}\) und Kantenmenge \(\{(v_1,v_2),...,(v_{k-1},v_k)\}\). Ein gerichteter Kreis ist also \(C^k = P^{k-1} + (v_{k-1}, v_0)\).

Ein gerichteter, kreisfreier Graph hat den Spezialbegriff DAG. In jedem DAG existiert mindestens ein Knoten \(q\) mit \(d^-_G(q)=0\): die Quelle. Und es existiert mindestens ein Knoten \(s\) mit \(d^+_G(s)=0\): die Senke. Jeder DAG verfügt über mindestens eine topologische Sortierung, welche eine Reihenfolge \((v_1, ..., v_n)\) aller Knoten des Graphen darstellt, die die Eigenschaft erfüllt, dass nur Kanten der Form \((v_i, v_j)\) mit \(j>i\) existieren.
Gewichtete Graphen
Approximierte Fahrzeiten in Minuten modelliert als vollständiger, gewichteter Graph \(W\).
Nehmen wir wieder zwei Orte \(a,b\), die nun über eine direkte Straße von 1 km und einer direkten Umgehungsstraße von 3 km verbunden sind. Es ergibt sich intuitiv die Fragestellung, nicht nur einen Weg von \(a\) nach \(b\) zu finden, sondern eben einen kürzesten Weg. Unser herkömmliches Graphmodell erweitern wir dazu um eine Gewichtsfunktion \(w\colon E \rightarrow \mathbf{R}\), so dass wir einen gewichteten Graphen als \(G = (V,E,w)\) beschreiben. Die Wichtungen sind natürlich nicht nur auf Weglängen beschränkt, sondern können jede messbare Entität darstellen.

Die zusätzliche Wichtung eröffnet vielen bereits besprochenen Problemfeldern eine neue Optimierungsdimension. Man sucht nun zum Beispiel minimale/maximale Spannbäume und den kürzesten \(a\)-\(b\)- oder Hamilton-Weg. Kombiniert man einen gerichteten, kreisfreien Graphen (DAG) mit zusätzlichen Kantengewichten, dann handelt es sich um ein Netzwerk, welches man auf die maximal-übertragbare Kapazität zwischen einer Quelle und einer Senke untersuchen kann.

(
)
Beweise die oben postulierte Aussage, dass jeder gerichtete, kreisfreie Graph \(G = (V,E)\) mindestens eine Quelle \(q\) mit \(d_G^-(q) = 0\) enthält. Schlussfolgere daraus, dass auch eine Senke \(s\) vorhanden sein muss.
Hinweise
Nimm an, jeder Knoten besitzt mindestens eine eingehende Kante, und führe das zum Widerspruch.
Beispiellösung

Ich nehme an, für jeden Knoten \(v_i\) gilt \(d_G^-(v_i) \geq 1\). Dann wähle ich ein beliebiges \(v_i\) und traversiere rückwärts zum Knoten \(v_{i-1}\) für den \((v_{i-1},v_i)\) in \(E\) liegt. Da jeder Knoten per Annahme mindestens einen solchen adjazenten Knoten besitzt und \(G\) aber azyklisch und endlich ist, muss irgendwann ein letzter Knoten \(v_0\) mit \(d_G^-(v_0) = 0\) erreicht sein. Damit ist ein Widerspruch erzeugt, \(v_0\) ist die Quelle.

Die Existenz einer Senke lässt sich mit analoger Argumentation für den Ausgangsgrad zeigen.


Ende des Lehrinhalts, unten findest du weiterführendes Material

I. Quellen und weiterführendes Material

Neben zahlreichen Wikipedia-Artikeln aus dem Themengebiet der Graphentheorie existieren weitere Ressourcen, die wir zum tiefgehenderen Studium besonders empfehlen:

R. Diestel - Graphentheorie (Springer, 2000)
Standardwerk mit allen Termini, wichtigen Beweisen und Aufgaben.
Zusammenfassung Graphentheorie aus Diskrete-Strukturen II (Uni Jena, 2014)
Zusammenfassung aller wichtigen Termini von mir akkumuliert aus dem Diestel und Wikipedia von den hier behandelten Grundbegriffen bis zu Minoren, Cliquen, DAGs, Färbungen und planaren Graphen.
A. Schwartz - Einführung in die Graphentheorie (Uni Würzburg, 2013)
Ausführliches Einführungswerk geeignet für Neulinge wegen einleitender Erklärung der Aussagenlogik und wichtiger Beweiskonzepte. Erstreckt sich bishin zu wichtigen graphtheoretischen Algorithmen.
Emden-Weinert, Hougardy, Kreuter, Prömel, Steger - Einführung in Graphen und Algorithmen (Uni Berlin, 1996)
Nach sehr knapper graphentheoretischer Einführung werden alle Felder der Algorithmik mit Graphen ausführlichst beleuchtet. Gut zum Nachschlagen.