Einführung in die Graphentheorie – Akademischer Tag 3

Der Begriff „Graph“ tauchte schon häufiger auf phphatesme.com auf, weshalb ich den Begriff ein wenig formaler erklären möchte. Bei der sog. Graphentheorie handelt es sich lt. Wikipedia um ein „Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht“. Da die theoretische Informatik viel mit der Mathematik gemein hat, ist eine Einführung sehr gut für den Akademischen Tag geeignet.

Bevor wir mit der Theorie beginnen, möchte ich dieses Thema motivieren, da die Graphentheorie in sehr vielen Bereichen der Informatik eingesetzt werden kann. Sie schlägt sich innerhalb der praktischen Informatik nicht nur in Algorithmen oder Datenstrukturen (wie z.B. dem allseits bekannten Baum) nieder, sondern auch in diversen UML-Diagrammen. Das bekannte Klassendiagramm kann genauso wie ein Graph aufgefasst werden wie ein Aktivitätsdiagramm. Insgesamt lassen sich Graphen sehr gut zur Modellierung von Problemen und deren Lösung nutzen. Mithilfe der Komplexitätstheorie lässt sich sogar für einige Probleme beweisen, dass sie nicht effizient lösbar sind. Da die Graphentheorie sehr vielschichtig ist, möchte ich in diesem einführenden Artikel vor allem grundlegende Graphen erklären und darauf eingehen, wie man diese in einem Computer darstellen kann. In den weiteren Artikeln zur Graphentheorie sollen dann die o.g. Themen sowie praktische Algorithmen auf Graphen vertieft werden.

Als erstes stellt sich die Frage, was ist denn nun ein Graph? Vereinfacht gesagt: Ein Gebilde aus Knoten und Kanten, d.h. Punkten und Linien, die jeweils zwei (nicht notwendigerweise unterschiedliche) Punkte verbinden. Die abstrakte Beschreibung lässt noch nicht viel erahnen, wie ein solche Graph aussieht, weshalb ich auf eine Visualisierung eines Graphen verweisen möchte:

Graph mit sechs Knoten

Hier sieht man, was die Knoten und was die Kanten sind. Das interessante an solchen Darstellungen ist, dass es theoretisch unendlich viele Darstellungen eines Graphs gibt, sodass man den Graphen auch völlig anders hätte anordnen können. Im wesentlichen geht es darum, dass in jeder dieser Darstellungen die gleichen Knoten miteinander verbunden sind. Es gibt in der Informatik sogar eine eigene Disziplin, die sich mit dem Zeichnen von Graphen beschäftigt, das sog. graph drawing.

Da wir nun wissen, wie sich Graphen visualisieren lassen, sollte auch noch geklärt werden, wie sich Graphen definieren lassen. Die allgemeinste Formulierung ist: G = (V,E) ist ein Graph. V entspricht der Menge der Knoten (engl. vertices) und E der Menge der Kanten (engl. edges). D.h. der Graph G besteht aus der Knotenmenge V und der Kantenmenge E. Sei G = (V,E) der Graph, der durch obige Grafik dargestellt ist, so ist V = {1,2,3,4,5,6} und E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4], {4,5}, {4,6}}. Für jede Kante {x,y} ∈ E gilt, dass x und y durch eine Kante miteinander verbunden sind. Durch die Mengenschreibweise wird klar, dass {x,y} = {y,x} gilt und somit die Reihenfolge der durch die Kanten verbundenen Knoten nicht von Belang ist. Wir sprechen in diesem Fall von einem ungerichteten Graphen.

Ein praxisrelevantes Beispiel für einen ungewichteten Graphen wurde bereits in einem anderen Artikel gegeben:  Six Degrees of Separation (friend of a friend). Dabei stellte jede Person im sozialen Netzwerk einen Knoten dar und eine Kante zwischen zwei Personen existierte genau dann, wenn die beiden Personen befreundet waren. Das zu lösende Problem bestand darin, herauszufinden über wie viele Ecken man einen anderen Benutzer kennt – dabei war natürlich die geringste Anzahl von Ecken gefragt. Graphentheorisch formuliert, lautete das Problem, das sog. kürzester Weg-Problem zu lösen, was im konkreten Fall durch den  Dijkstra-Algorithmus geschah. D.h. man sucht den kürzesten Weg von einem Knoten zu einem anderen Knoten.

Im Gegensatz zu den ungerichteten Graphen gibt es natürlich auch gerichtete Graphen, bei denen die Kanten eine Richtung besitzen. Ein Beispiel hierfür ist der folgende Graph:

Gerichteter Graph

Formal entspricht der obige Graph G = (V, E) mit V = {A,B,C,D,E,F} und E = {(A,B), (B,C), (C,E), (D,B), (E,D), (E,F)}. Für jede gerichtete Kante (x,y) ∈ E gilt, dass eine Kante von x nach y führt. Aus der Tupelschreibweise folgt, dass die Richtung relevant ist, da (x,y) ≠ (y,x) gilt, wenn x ≠ y. Verschiedene Arten von Graphen unterscheiden sich also in der Definition ihrer Kanten.

Da jeder Webentwickler bereits mit Datenbanken gearbeitet haben wird, sollte jedem derselben referentielle Integrität bekannt sein. Das Ziel ist es, in jedem Zustand zu gewährleisten, dass zu jeder Zeile einer Tabelle die referenzierten Zeilen existieren. Verwendet man eine Löschweitergabe (CASCADE DELETE), so soll in jedem Schritt die referentielle Integrität gewährleistet sein. Auch dieses Problem lässt sich auf einen Graphen abstrahieren: Jede Zeile stellt einen Knoten dar und zwischen einer Zeile A und einer Zeile B existiert genau dann eine gerichtete Kante von A nach B, wenn A auf B referenziert. Auf Grundlage eines solchen Graphen lässt sich dann ein Algorithmus, das sog. Topologische Sortieren, anwenden, der eine Löschreihenfolge bestimmt ohne die referentielle Integrität zu gefährden.

Die beiden bisher beschriebenen Arten von Graphen lassen sich noch um den Zusatz gewichtet erweitern. Bei einem gewichteten Graphen existiert eine Gewichtsfunktion f: E → R, die jeder Kante einen (reellen) Wert zuordnet, wie der folgende gewichtete Graph zeigt:

Ungerichteter gewichteter Graph

Das Erkennen der Knoten- bzw. Kantenmenge sollte keine Probleme mehr bereiten, deshalb wird lediglich gezeigt, wie die Gewichtsfunktion f definiert ist:

• f({1,2}) = f({2,1}) = 2
• f({1,4}) = f({4,1}) = 5
• f({2,3}) = f({3,2}) = 14
• f({2,4}) = f({4,2}) = 5
• f({2,5}) = f({5,2}) = 4
• f({3,5}) = f({5,3}) = 34
• f({4,5}) = f({5,4}) = 58

Ein häufiges Einführungsbeispiel sind Straßennetze, die graphentheoretisch modelliert werden können. Jeder Knoten entspricht dabei einer Kreuzung und eine Kante zwischen zwei Kreuzungen existiert genau dann, wenn diese Kreuzungen direkt durch eine Straße miteinander verbunden sind. Um Einbahnstraßen zu berücksichtigen wäre hierbei ein gerichteter Graph zweckmäßig. Außerdem erhält jede Kante ein Gewicht, welche die Länge des Straßenabschnitts angibt. Um den kürzesten Weg zu finden, wie es beispielsweise Routenplaner tun, lässt sich auf diesem Graphen ein Algorithmus zur Bestimmung des kürzesten Pfads auf gewichteten Graphen anwenden, wie z.B. der bereits genannte Dijkstra-Algorithmus oder der besser geeignete A*-Algorithmus.

Da jetzt die grundlegendsten Typen von Graphen geklärt sind, können wir zur Darstellung von Graphen innerhalb eines Programms kommen. Die wahrscheinlich bekannteste Darstellung ist die Adjazenzliste (wörtlich Nachbarschaftsliste), in der jedem Knoten eine Liste von benachbarten Knoten zugeordet wird. In PHP lässt sich dies mithilfe von Arrays sehr einfach lösen. Der gerichtete Graph ließe sich folgendermaßen in PHP-Code denotieren:

$adj = array(
	'A' => array('B'),
	'B' => array('C'),
	'C' => array('E'),
	'D' => array('B'),
	'E' => array('D','F'),
	'F' => array()
);

Über $adj[$x] erhält man die Nachbarn des Knotens $x. Ungerichtete Graphen lassen sich analog definieren: Existiert zwischen x und y eine Kante, so ist y in der Nachbarschaftsliste von x und x ist in der Nachbarschaftsliste von y. Der erste ungerichtete Graph wäre somit folgendermaßen denotiert:

$adj = array(
	1 => array(2,5),
	2 => array(1,3,5),
	3 => array(2,4),
	4 => array(3,5,6),
	5 => array(1,2,4),
	6 => array(4)
);

Eine solche Darstellung eignet sich für viele Algorithmen. Allerdings gibt es eine weitere Darstellung, die vor allem mit der objektorientierten Programmierung assoziiert ist. Das Prinzip ist sehr ähnlich zu dem von Adjazenzlisten, aber der große Unterschied besteht darin, dass jeder Knoten durch ein Objekt repräsentiert wird und jeder Knoten in der Lage ist, seine Nachbarn zurückzugeben. Diese Variante ist vor allem dann nützlich, wenn ein Knoten mehr als nur ein primitiver Wert ist. Folgender PHP-Code, der den gerichteten Graphen darstellt, sollte diese Idee verdeutlichen:

class Node {
	private $identity = null;
	private $neighbours = array();

	public function __construct ($identity) {
		$this->identity = $identity;
	}

	public function connect (Node $node) {
		$this->neighbours[] = $node;
		return $this;
	}

	// Getter & Setter ...
}
$a = new Node('A');
$b = new Node('B');
$c = new Node('C');
$d = new Node('D');
$e = new Node('E');
$f = new Node('F');
$a->connect($b);
$b->connect($c);
$c->connect($e);
$d->connect($b);
$e->connect($d)->connect($f);

Da wir nun computerinterne Darstellungen von Graphen kennen, können wir auf diesen auch Algorithmen ausführen, die allerdings in weiteren Artikeln weitergeführt werden müssen, da der Rahmen keine ausführliche Beschreibung von grundlegenden Algorithmen mehr zulässt. Wer Vorschläge in Richtung bestimmter Themen hat, darf sich natürlich gerne in den Kommentaren äußern.