Graphentheorie

Geschrieben von Pascal Sommer, Raphael Fischer und Daniel Graf.

Graphen sind ein wichtiger Bestandteil vieler Aufgaben in der Informatik, und haben in diversen Gebieten praktische Anwendungen. Als Graph bezeichnen wir ein Netzwerk aus Punkten und Verbindungen dazwischen, zum Beispiel den Strassenplan einer Stadt. Die Punkte stehen dann für die Kreuzungen und Plätze der Stadt und die Verbindungen für die Strassen dazwischen.

Was wir häufig wissen wollen ist zum Beispiel der kürzeste Weg zwischen zwei Punkten (Wie komme ich am schnellsten zum Bahnhof?) oder ob es überhaupt möglich ist, von jedem Ort an jeden anderen zu kommen (Gibt es eine Insel von der man nicht mehr wegkommt?).

Manchmal sind noch Zusatzinformationen zu den Knoten und Kanten gegeben, zum Beispiel eine Fahrtzeit pro Kante (ein sogenanntes Kantengewicht) oder eine Richtung pro Kante (z.B. für Einbahnstrassen). Für den Anfang beschäftigen wir uns aber nur mit ungerichteten, ungewichteten Graphen.

Problembeschreibung

Was ist ein Graph?

Als Graphen bezeichnen wir eine Menge von Punkten und Verbindungen zwischen diesen Punkten. Die Punkte werden meist Knoten und die Verbindungen zwischen zwei Punkten meist Kanten genannt. Im Bild 1 siehst du ein Beispiel eines solchen Graphen. Jeder Kreis ist ein Knoten und jede Linie, die zwei solcher Knoten verbindet, ist eine Kante.

Bild 1: Ein Beispiel für einen Graphen mit 6 Knoten und 5 Kanten.

Dieser Graph besteht also aus 6 Knoten und 5 Kanten. Eine der fünf Kanten verläuft zwischen Knoten \(2\) und \(3\), daher sagen wir, dass Knoten \(2\) und Knoten \(3\) benachbart sind. Die beiden Knoten sind auch indirekt benachbart, nämlich über den gemeinsamen Nachbarn \(4\). Häufig sprechen wir von der Nachbarschaft eines Knotens, was die Menge aller direkten Nachbarn dieses Knotens bezeichnet. Die Nachbarschaft von \(3\) sind die Knoten \(1\), \(2\) und \(4\) und die Nachbarschaft von \(2\) sind die Knoten \(3\) und \(4\).

Auf die genaue Zeichnungsart des Graphen kommt es uns aber gar nicht an. Ob zwei Darstellungen den gleichen Graph representieren, hängt nur davon ab, dass beide die gleichen Knoten haben und jeweils die gleichen Knotenpaare verbunden sind. Wenn wir also die Knoten ein wenig verschieben und die Kanten entsprechend mitbewegen, sagen wir immer noch, dass dies derselbe Graph ist. Es muss auch gar nicht unbedingt eine solche Zeichnung sein, wir können einen Graphen auch einfach als Liste von Knoten und Kanten beschreiben. Dazu benennen wir oft die Knotenmenge mit \(V\) (Englisch vertices) und die Kantenmenge mit \(E\) (Englisch edges). Das Beispiel im Bild 1 wäre dann \(V = \{1,2,3,4,5,6\}\) und \(E=\{ \{1,3\}, \{2,3\}, \{2,4\}, \{3,4\}, \{5,6\} \}\). Die Anzahl Knoten bezeichnen wir meist mit \(n\) (im Beispiel ist \(n=6\)) und die Anzahl Kanten mit \(m\) (im Beispiel ist \(m=5\)).

Wie sieht ein Graph im Computer aus?

Wenn wir nun in einer Aufgabe einem solchen Graphen begegnen, ist dieser meist nicht als Bild gegeben, sondern als eine abstrakte Auflistung der Knoten und Kanten. Die Knoten sind dann meist von \(1\) bis \(n\) nummeriert. Die Eingabe beginnt mit einer Zeile mit \(n\) und \(m\), danach folgen \(m\) Zeilen mit den Punktepaaren der \(m\) Kanten. Etwa so (für das Beispiel in Bild 1):

6 5
1 3
2 3
2 4
3 4
5 6

Und was machen wir jetzt damit? Wie repräsentieren wir diesen Graphen in unserem Programm, sodass wir nützliche Dinge damit anstellen können? SOI-typische Graphenaufgaben haben oft bis zu \(100'000\) Kanten, wir können also nicht einfach alle Kanten in eine grosse Liste werfen, und bei jeder Abfrage die ganze Liste durchgehen. Eine nützliche Speicherart für Graphen ist eine sogenannte Adjazenzliste. Die Idee ist simpel: wir merken uns für jeden Knoten eine separate Liste mit all seinen Nachbarn. Die Datenstruktur besteht also aus \(n\) Listen, und wenn wir die Nachbarschaft des Knotens \(x\) wissen wollen, schauen wir die \(x\)-te dieser Listen an. Die Listen für das Beispiel aus Bild 1 sähe damit so aus:

1 : 3
2 : 3, 4
3 : 1, 2, 3
4 : 2, 3
5 : 6
6 : 5

Implementieren lässt sich das in C++ ganz leicht mittels Vektoren (Arrays dynamischer Grösse; hat nicht viel mit den Vektoren aus der Mathe zu tun). Wir verschachteln dazu \(n\) Vektoren in einen grossen Vektor - die inneren Vektoren sind die Nachbarschaftslisten und der äussere Vektor hält sie alle zusammen. Ein wenig müssen wir noch wegen der nullbasierten Indexierung aufpassen: entweder wir wandeln alles in nullbasierte Indexierung um (was häufig einfacher geht), oder wir fügen einfach noch einen zusätzlichen Knoten \(0\) ohne Nachbarn hinzu:

int n, m;
cin >> n >> m;

// Erste Variante mit nullbasierte Knoten (von 0 bis n-1 nummeriert):
vector<vector<int> > graph (n);
for(int i = 0; i < n; ++i){
    int a, b;
    cin >> a >> b;

    // hier ändern wir die Nummerierung von 1 bis n zu 0 bis n-1
    a--;
    b--;

    graph[a].push_back(b);
    graph[b].push_back(a);
}


// oder mit einem 0-ten Knoten ohne Nachbarn:
vector<vector<int> > graph (n+1);
for(int i = 0; i < n; ++i){
    int a, b;
    cin >> a >> b;

    graph[a].push_back(b);
    graph[b].push_back(a);
}
// Die Nachbarn von Knoten x sind dann in graph[x] zu finden.

Grundbegriffe der Graphentheorie

Im Rest dieses Kapitels geht es nun um die genauere Betrachtung eines Graphen aus mathematischer Sicht und dessen Eigenschaften.

Mathematische Beschreibung eines Graphen

Wie schon oben beschrieben, besteht ein Graph mathematisch betrachtet aus zwei Mengen: Die Menge der Knoten \(V\) (von “vertices” auf Englisch) und die Menge der Kanten \(E\) (von “edges”). Dabei ist jede Kante wiederum eine Menge von genau zwei Knoten, nämlich die Knoten, die die Kante verbindet. Wir bezeichnen nun die Anzahl der Knoten eines Graphs mit \(|V|\) oder \(n\) und die Anzahl der Kanten mit \(|E|\) oder \(m\).

Nehmen wir nun zum Beispiel folgenden kleinen Graphen:

%3 a a b b a--b c c b--c

Hier ist nun \(V = \{a, b, c\}\) und \(E = \{\{a,b\}, \{b,c\}\}\)

Zwei wichtige Begriffe sind Adjazenz und Inzidenz: Wir sagen, dass zwei Knoten adjazent sind, falls eine Kante zwischen ihnen existiert, sie quasi “Nachbarn” sind. Ein Knoten und eine Kante sind inzident, falls der Knoten ein Endpunkt der Kante ist.

Multigraph

Dies ist eine etwas allgemeinere Form eines Graphen, die auch Schlingen (Kante von einem Knoten zu sich selber) und Mehrfachkanten (mehrere Kanten zwischen den gleichen zwei Knoten) zulässt. Folgender Graph hat Schlingen (von \(a\) nach \(a\)) und Mehrfachkanten (zwischen \(b\) und \(c\)):

%3 a a a--a a--a b b a--b c c b--c c--a c--b

Ein Graph, der keine Schlingen und Mehrfachkanten besitzt ist ein einfacher Graph. Solange nicht explizit darauf hingewiesen wird, werden wir in diesem Skript von einfachen Graphen ausgehen.

Grad eines Knoten

Der Grad eines Knoten wird mit deg\((u)\) bezeichnet (von Englisch “degree”) und ist die Anzahl Kanten, die zu diesem Knoten verbinden. So ist zum Beispiel deg\((a) = 3\) in folgendem Graphen:

%3 a a b b a--b d d a--d c c b--c c--a

Pfad

Ein Pfad der Länge \(l\) in einem Graphen ist, mathematisch gesagt, eine Folge von \(l+1\) verschiedenen Knoten eines Graphen, sodass zwei aufeinander folgende Knoten jeweils durch eine Kante verbunden sind.

Im folgenden Graph ist als Beispiel ein Pfad der Länge 2 markiert:

%3 a a b b a--b c c a--c d d b--d b--c

Zusammenhang

Ein Graph ist zusammenhängend, falls zwischen allen Paaren von Knoten ein Pfad existiert. Dieser Begriff sollte im nächsten Abschnitt noch etwas klarer werden.

Zusammenhangskomponenten

Intuitiv ist dieser Begriff sehr einfach: So hat zum Beispiel obiger Graph nur eine Zusammenhangskomponente, während folgender deren drei hat:

%3 a a b b c c b--c d d e e d--e f f d--f

(Beachte, dass dies nicht drei verschiedene Graphen sind, sondern eben ein Graph mit drei Zusammenhangskomponenten!)

Einen Graph kann man in seine Zusammenhangskomponenten separieren, ohne dabei eine Kante zu zertrennen.

Es folgt daraus, dass ein Graph genau dann zusammenhängend ist, wenn er genau eine Zusammenhangskomponente hat.

Zyklus

Ein Zyklus oder Kreis ist ähnlich wie ein Pfad, nur dass Anfangs- und Endknoten derselbe sind. In folgendem Graphen ist ein Zyklus der Länge 4 markiert:

%3 a a b b a--b e e a--e c c b--c d d b--d c--d d--a e--d

Zyklische und Azyklische Graphen

Ein Graph, der mindestens einen Zyklus enthält, heisst zyklischer Graph. Analog heisst ein Graph, der keinen Zyklus enthält, azyklischer Graph.

Gewichteter Graph

Bei einem gewichteten Graphen besitzt jede Kante zusätzlich eine Zahl, ein sogenanntes Gewicht. Typische Anwendungszwecke sind Fahrzeiten über Strassen oder Bandbreiten von Netzwerkverbindungen.

Hier als konkretes Beispiel das vereinfachte Tramnetz von Zürich mit den Fahrzeiten in Minuten: image0

Spezielle Graphen

Bäume

Ein spezieller Typ von Graph, der sehr oft gebraucht wird, ist der Baum: Ein Baum ist ein azyklischer, zusammenhängender Graph.

Spezielle Knoten

Ein Knoten mit Grad 1 (es geht also genau eine Kante von ihm weg), wird als Blatt bezeichnet.

Oft wird ein bestimmter Knoten eines Baumes als Wurzel bezeichnet. Diese ist sozusagen der “Hauptknoten” von dem alle anderen Knoten ausgehen. Anders als bei einem biologischen Baum wird in der Informatik ein Baum mit der Wurzel zuoberst dargestellt:

%3 a a_Wurzel b b a--b c c_Blatt a--c d d a--d e e_Blatt b--e f f_Blatt b--f g g_Blatt d--g

Beachte, dass die Wurzel auch ein Blatt sein kann!

Ein typisches Beispiel für einen Graphen ist das Dateisystem eines Computers. Das Root-Verzeichnis ist dort die Wurzel, Dateien (oder leere Ordner) sind Blätter und nicht-leere Ordner sind alle anderen Knoten.

Eigenschaften

Eine wichtige Eigenschaft eines Baumes ist, dass immer gilt \(|E| = |V| - 1\), also \(Anzahl Kanten = Anzahl Knoten - 1\). Man kann sich das klar machen, indem man sich den Baum mit der Wurzel zuoberst vorstellt. Dann hat jeder Knoten genau eine Kante direkt über sich ausser die Wurzel.

Vollständige Graphen

Zu einer gegebenen Anzahl Knoten gibt es genau einen vollständigen Graphen: Er ist dadurch charakterisiert, dass es zwischen allen Knotenpaaren eine Kante gibt, der Graph enthält also die grösstmögliche Anzahl Kanten. Wie man sich leicht überlegen kann, ist der Grad jedes Knotens \(n - 1\). Als Veranschaulichung hier ein vollständiger Graph mit \(n = 5\): image1

Bipartite Graphen

Ein bipartiter Graph ist ein Graph, dessen Knoten in zwei Mengen aufgeteilt werden können, sodass innerhalb einer Menge keine zwei Knoten durch eine Kante verbunden sind (es verlaufen also alle Kanten zwischen den Mengen). Folgender Graph ist zum Beispiel bipartit:

%3 cluster_0 cluster_1 a a d d a--d e e a--e b b b--e c c c--e

Implementation von Graphen

Oben wurde schon die am häufigsten verwendete Methode um einen Graph zu speichern, die Adjazenzliste beschrieben. Es gibt allerdings noch eine weitere Methode, die meist langsamer ist, in einigen Anwendungsfällen jedoch schneller:

Adjazenzmatrix

Im Gegensatz zur Adjazenzliste legt man keine Liste aller Knoten an, sondern eine Matrix bzw. Tabelle mit \(n\) Zeilen und \(n\) Spalten. Jede Zeile bzw. Spalte steht dabei für einen Knoten. Im einfachsten Fall hat jedes Datenfeld der Tabelle den Typ bool (“wahr” oder “falsch”), der aussagt, ob der Knoten seiner Zeile mit dem Knoten seiner Spalte verbunden ist. Wenn Knoten \(i\) mit Knoten \(j\) verbunden ist, ist auch Knoten \(j\) mit Knoten \(i\) verbunden. Das heisst, es gibt pro Kante immer zwei bools, die true sind und die Matrix ist für ungerichtete symmetrisch bezüglich der Diagonalen. Je nach dem kann es den Code vereinfachen, wenn nur der Teil über oder unter der Diagonalen betrachtet wird. So muss man nicht immer zwei bools schreiben.

Gewichtete Graphen

Falls ein gewichteter Graph implementiert werden soll, kann bei der Adjazenzmatrix der bool durch int ersetzt werden. Allerdings braucht es dann einen speziellen Wert, z.B. -1, der bedeutet, dass dort keine Kante existiert.

Bei der Implementierung als Adjazenzliste ist die Umstellung ein bisschen aufwendiger: Hier muss jeder Integer, der auf einen anderen Knoten verweist, durch ein pair ersetzt werden. Dabei steht der erste Wert für den Nachbarknoten, der zweite für das Gewicht dieser Kante.

Vergleich Adjazenzmatrix vs. Adjazenzliste

Der Speicherverbrauch der Adjazenzmatrix ist \(\mathcal O(n^2)\), da dies gerade die Grösse der Matrix ist. Alle oben implementierten Operationen haben eine konstante Laufzeit, allerdings ist die Laufzeit um alle Kanten eines Knoten zu finden \(\mathcal O(n)\).

Ein Vergleich der beiden Speichervarianten sieht dann so aus: | Operation | Adjazenzliste | Adjazenzmatrix | |:——|:———–:|:—:| | Speicherplatz | \(\mathcal O(n+m)\) | \(\mathcal O(n^2)\) | | Kante einfügen | \(\mathcal O(1)\) | \(\mathcal O(1)\) | | Kante löschen | \(\mathcal O(m)\) | \(\mathcal O(1)\) | | Prüfen ob Kante existiert | \(\mathcal O(m)\) | \(\mathcal O(1)\) | | Finde alle Kanten eines Knoten | \(\mathcal O(m)\) | \(\mathcal O(n)\) | | Graph traversieren (BFS/DFS) | \(\mathcal O(n+m)\) | \(\mathcal O(n^2)\) | Zu dieser Tabelle gibt es einige Kommentare: * Wenn in der Aufgabenstellung keine Beschränkung gegeben ist, gilt \(E \in \mathcal O(V^2)\). Falls wir es also mit einem dichten Graph (d.h. mit sehr vielen Kanten) zu tun haben, sind die beiden Varianten praktisch gleich gut. * In den allermeisten Fällen an der SOI gibt es keine dichten Graphen und Speicherplatz sowie das Besuchen der Kanten ist entscheidend. In diesem Fall ist die Adjazenzliste die bessere Wahl. * Ein möglicher Fall, bei dem man die Adjazenzmatrix statt der -liste verwenden sollte, ist wenn es genügend Speicherplatz gibt, zu Beginn ein Graph eingelesen wird und es danach Abfragen gibt, ob eine gewisse Kante existiert.

Gerichtete Graphen

Ein Graph kann auch gerichtet sein. Das bedeutet, dass jede Kante eine Richtung besitzt. Sie wird nun als Pfeil dargestellt. Aussderdem haben gerichtete Graphen einen eigenen Namen: Digraphen (Abkürzung von Englisch “directed graph”). Bei einem Pfad von \(A\) nach \(B\) müssen nun alle Kanten in Pfadrichtung orientiert sein. Ausserdem kann es nun zwischen zwei Knoten auch zwei Kanten geben so lange sie in unterschiedliche Richtungen zeigen.

Zyklen

Genau so, wie sich die Eigenschaft eines Pfades ändert, ändert sich auch die Eigenschaft eines Zyklus. Wird in einem zyklischen, ungerichteten Graphen jeder Kante eine Richtung zugewiesen, muss der neue, nun gerichtete Graph, nicht unbedingt zyklisch sein So ist zum Beispiel folgender Graph nicht zyklisch, da man z.B. in einem Strassennetz mit diesem Layout nicht mehr im Kreis fahren könnte:

%3 a a b b a->b c c a->c b->c

Eingangs- und Ausgangsgrad

Auch die Eigenschaft des Grads eines Knotens verändert sich etwas: Es gibt nun den Eingangsgrad - die Anzahl Kanten die zu einem Knoten führen - und den Ausgangsgrad - die Anzahl ausgehender Kanten.

Implementierung

Die Implementierung ist ziemlich intuitiv: Bei der Adjazenzliste enthält \(a\) einen Eintrag zu Knoten \(b\), wenn es eine Kante von \(a\) in Richtung \(b\) gibt. Die Adjazenzmatrix ist nicht mehr symmetrisch zur Diagonale. Nun muss man sich entscheiden, ob der erste Index des Matrix-Zugriffs “von” oder “nach” bedeutet. Falls man sich für die “von”-Variante entscheidet, könnte der Code so aussehen:

// es existiert eine Kante von Knoten `a` zu `b`
graph[a][b] = true;

// von `b` zu `a` führt aber keine direkte Kante
graph[b][a] = false;

Quelle und Senke

Speziell für die in einem anderen Skript vorgestellte topologische Sortierung wird der Begriff der Quelle und Senke wichtig sein: Eine Quelle ist ein Knoten, der Eingangsgrad null besitzt, eine Senke hat Ausgangsgrad 0:

%3 b b_Quelle c c_Senke b->c a a b->a d d b->d a->d d->c

DAGs

Eine Unterklasse der Digraphen sind die azyklischen Digraphen, kurz DAGs (Abkürzung von “directed acyclic graph”). Alle DAGs besitzen mindestens eine Quelle sowie eine Senke. Das kann man sich so klar machen, dass man bei irgend einem Knoten beginnt, dann einer beliebigen Kante folgt und das immer wieder macht. Man kann nie bei einem schon besuchten Knoten landen, sonst hätte man einen Zyklus. Man darf das aber auch nicht ewig tun können, sonst wäre der Graph unendlich gross. Also kommt man irgendwann zu einem Knoten mit Ausgangsgrad 0, also einer Senke. Für die Quelle funktioniert das analog.

Sätze über Graphen

Es ist praktisch, die folgenden Sätze einmal gelesen zu haben. Allerdings lohnt es sich nicht, viel Aufwand zu investieren, sie sich zu merken. Denn entweder werden sie quasi selbstverständlich, wenn man eine Weile mit Graphen gearbeitet hat, oder man braucht sie recht selten.

  • Es gilt, dass die Summe der Grade aller Knoten gleich \(2m\) ist, oder als Formel: \(\sum \limits_{u \in V} deg(u) = 2m\) Das folgt aus der Überlegung, dass bei dieser Summe alle “Kanten-enden” gezählt werden. Da ja jede Kante genau zwei Enden hat, ist die Summe gleich \(2m\).
  • Aus dem obigen Satz folgt automatisch, dass die Anzahl der Knoten mit ungeradem Grad gerade sein muss.
  • Jeder Graph enthält mindestens \(n - m\) viele Zusammenhangskomponenten. Diesen Satz kann man durch Induktion herleiten: Man nimmt einen Graphen, der nur aus einem Knoten besteht. Für diesen stimmt der Satz. Nun fügt man einen neuen Knoten ohne Kante hinzu. Dann steigt sowohl die Anzahl der Zusammenhangskomponenten als auch \(n-m\) um eins. Er stimmt also weiterhin. Man kann auch einen Knoten mit einer Kante an eine bestehende Komponente hinzufügen. Dann verändert sich die Anzahl Zusammenhangskomponenten und \(n-m\) nicht. Die anderen Fälle kann man sich analog überlegen.
  • Aus obigem Satz folgt, dass für jeden zusammenhängenden Graphen gilt \(m \geq n - 1\).
  • Ein einfacher Graph kann nie mehr als \(\frac{n(n-1)}{2}\) Kanten haben. Beweis: Ein vollständiger Graph hat die maximale Anzahl Kanten und für diesen gilt \(deg = n-1\) für alle Knoten. Die Summe der Grade aller Knoten ist deshalb \(n(n-1)\). Aus dem ersten Satz folgt nun \(m \leq \frac{n(n-1)}{2}\).