Informationen

Deine Fortschrittsanzeige

Der Balken beschreibt deinen Fortschritt beim Lösen aller Aufgaben. Schaffst du es, alle Fragen richtig zu beantworten?

---

Text-Legende

Hervorhebung im Text	Erklärung
Begriff	Begriffs-Definition/-Einführung
Begriff	Extra Erläuterung als Popup
Ausdruck	Quelltext oder Zeichenkette

---

Aufgaben-Legende

Alle Feedbacks, die für eine deiner Lösungen bekommen kannst. Zum abschicken der Lösung musst du davor auf Lösungen überprüfen drücken.

Eingabefeld	Feedback
	Richtige Antwort
	Bisher noch keine Eingabe oder falsches Eingabeformat
	Falsche Lösung, vielleicht auch falsches Eingabeformat.

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 welchem Knoten 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)\). Wir schreiben dann verkürzend \(G=(V,E)\). 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 gilt, dass \(\{v_1,v_2\} \in E\). Die Knoten \(v_1\) und \(v_2\) nennt man inzident zur Kante \(\{v_1,v_2\}\).

Die Anzahl aller inzidenten Kanten eines Knotens \(v\) nennt man den Knotengrad \(\mathrm{deg}_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.

\(T\) \(T[\{a,e,f\}]\) \(T-\{\{e,d\}\}\) \(T-e\) \(T+\{\{b,d\}\}\) \(T[c]\)

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 einen entsprechenden Knoten explizit der Knotenmenge eines Graphen hinzuzufügen, schreibt man auch \(G \cup \{v\}\) oder \(G+v\). Entnimmt man einen Knoten, also \(G' = G - v\), so enthält \(G'\) weder \(v\) noch die 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.

2. Pfade und Kreise

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

\(I\) \(C^4 = abdea\) \(C^3 = bcdb\) \(C^5 = abcdea\) \(P^4 = aedbc\)

Ein Weg oder auch Pfad der Länge \(k\) von \(v_1\) nach \(v_{k+1}\) bezeichnet einen nichtleeren Graphen \(P^k=(V_P,E_P)\) mit \(V_P = \{v_1,v_2,...,v_{k + 1}\}\) (wobei die Knoten paarweise disjunkt sind, also für alle \(i \neq j\) gilt, dass \(v_i \neq v_j\)) und \(E_P=\{\{v_1,v_2\},\{v_2,v_3\},...,\{v_k,v_{k + 1}\}\}\). Da \(V_P\) bzw. \(E_P\) den Pfad vollständig definieren, notieren wir einen Pfad oftmals einfach als Folge von Knoten oder Kanten.

Ähnlich zu einem Pfad bezeichnet man für einen Graphen \(G = (V, E)\) eine Knotenfolge \(P=v_1v_2...v_{k + 1}\), für die für alle \(i \leq k\) gilt, dass \(\{v_i, v_{i + 1}\} \in E\), als Kantenzug. Bei diesem dürfen also Knoten und Kanten mehrfach vorkommen.

Ausgehend von dieser Definition nennt man \(P^k\) einen \(A\)-\(B\)-Weg genau dann, wenn \(V_P\cap A = \{v_1\}\) und \(V_P\cap B = \{v_{k + 1}\}\) gilt. Analog dazu ist ein \(s\)-\(t\)-Weg ein \(A\)-\(B\)-Weg mit \(A=\{s\}\) und \(B=\{t\}\).

Der Abstand \(d_G(v_1,v_2)\) zweier Knoten \(v_1\) und \(v_2\) in \(G\) ist definiert als die minimale Kantenanzahl 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, v_1\}\), wobei der Weg \(P^{k - 1}\) gleichzeitig als Knotenfolge \(v_1,...,v_k\) und auch als Graph \(P^{k-1}=(\{v_1,v_2,...,v_k\}, \{\{v_1,v_2\},...,\{v_{k-1},v_k\}\})\) betrachtet werden kann. Erweitert man diesen Weg um die zusätzliche Kante \(\{v_k, v_1\}\), entsteht ein geschlossener Weg der Länge \(k > 1\): 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 spricht man von einem 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 ein Eulerkreis definiert.

// 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;

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 Knotenpaare \(a, b\) 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.

// 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;

forall pairs of Nodes (a, b) in G {
    if !existiertWeg(a,b,G) { return false; }
}
return true;

// 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;

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.

Bäume

Der maximal kreisfreie Graph \(B\): ein Baum.

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 Graphalgorithmen (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.

Oftmals ist es vorteilhaft, sich Bäume mit einer konkreten Ausrichtung vorzustellen: Beginnend in einem beliebigen Knoten — der Wurzel — werden alle Knoten in Ebenen angeordnet. Die Wurzel befindet sich ganz oben, darunter kommen die direkten Nachbarn der Wurzel, darunter deren Nachbarn und so weiter. Unsere Unit zu Heaps zeigt viele solche Baumdarstellungen. Die Knoten, die direkt unter einem anderen Knoten \(v\) hängen, heißen Kinder von \(v\); der Knoten \(v\) selbst ist deren Vater- oder Elternknoten. Die Kinder eines Knoten \(v\), deren Kinder und Kindeskinder usw. heißen Nachfahren von \(v\) und bilden gemeinsam mit dem Knoten selbst den in \(v\) gewurzelten Teilbaum.

Partite Graphen

Verschiedene Darstellungen partiter Graphen. Die einzelnen Partitionen sind farblich hervorgehoben.

\(K_{3,3}\) \(K_{3,3}\) \(K_{1,2}\) \(K_{1,2,3}\) \(K_{2,2,2}\)

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?

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 Paar \((a,b)\) definiert. Graphen können entweder nur ungerichtete oder gerichtete Kanten enthalten, man nennt sie dann ungerichtet respektive 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 + 1}\) ist nichts anderes als ein nichtleerer Graph mit Knotenmenge \(\{v_1,v_2,...,v_{k + 1}\}\) und Kantenmenge \(\{(v_1,v_2),...,(v_k,v_{k + 1})\}\). Ein gerichteter Kreis ist also \(C^k = P^{k-1} + (v_k, v_1)\). Wenn wir die Richtung aller Kanten eines gerichteten Graphen \(G\) umkehren, so erhalten wir den transponierten Graphen \(G^T\).

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 oder den kürzesten \(a\)-\(b\)- oder Hamiltonweg. 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.

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. Zu beachten ist, dass nicht überall dieselbe Notation verwendet wird.

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.

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.