Viele Probleme kannst du mithilfe von Graphen modellieren.
Wenn du ein Problem geeignet als Graph modelliert hast, kannst du die Standard-Algorithmen der Graphentheorie darauf anwenden und so die Lösung des Problems berechnen.
Ein Beispiel: Du modellierst das Straßennetz deiner Heimatstadt als einen Graphen. Dann brauchst du nur noch den Kürzeste-Wege-Algorithmus anzuwenden, wenn du von A nach B navigieren willst.
Ein Graph ist anschaulich dargestellt so etwas:
Formal gesehen besteht ein Graph aus einer endlichen, nichtleeren Menge von Knoten (die Kringel in der Darstellung) und einer Menge von Kanten (die Pfeile in der Darstellung).
Eine Kante ist eindeutig angegeben durch ihren Startknoten und ihren Endknoten. Damit lässt sich die Kante als Paar von zwei Knoten (dem Startknoten) und (dem Endknoten) angeben.
Der Graph aus der Abbildung besteht also aus der Knotenmenge und der Kantenmenge .
Formal gesehen ist ein Graph ein Paar , wobei eine endliche, nichtleere Menge von Knoten und die Menge der Kanten ist. Die Kanten sind Paare von je zwei Knoten; die Menge der Kanten ist also eine Teilmenge des kartesischen Produkts und damit eine Relation auf der Menge .
Diese Relation kannst du in Worten etwa mit "ist durch eine dorthin gerichtete Kante verbunden mit" ausdrücken.
Pfad, Weg
Wenn du in einem Graphen von einem Knoten entlang der Kanten zu einem Knoten gelangst, beschreitest du einen Pfad (oder Kantenzug). Achte darauf, dass du dabei die Kanten in Pfeilrichtung durchläufst.
Zum Beispiel ist ein Pfad der Länge 5 in dem oben gezeigten Graphen.
Baum
In der Informatik spielen Bäume eine herausragende Rolle. Denn viele Daten lassen sich als hierarchische Struktur modellieren, also als eine Struktur, die sich von einem Punkt aus verzweigt. Eine solche Struktur wird als Baum bezeichnet.
Der folgende gerichtete Graph ist ein Baum. Ein (gerichteter) Baum wird meist so gezeichnet, dass die Kanten von oben nach unten gerichtet sind.
Ganz oben siehst du den Knoten, zu dem keine Kante hinführt; dieser Knoten ist die Wurzel des Baums. Zu jedem anderen Knoten führt genau eine Kante hin. Und außerdem enthält der Graph keinen Kreis. Er ist somit ein Baum.
Ferner erkennst du in dem Baum einige Knoten, von denen keine Kante wegführt; diese Knoten sind die Blätter des Baums (hier grün, wie Blätter nun einmal normalerweise sind, dargestellt). Alle anderen Knoten des Baums heißen innere Knoten.
Beispielsweise hat der oben gezeigte Baum die Tiefe 3.
Binäre Bäume
In der folgenden Abbildung siehst du einen vollständigen binären Baum der Tiefe 3:
Manchmal ist auch die letzte Schicht in einem vollständigen binären Baum "angeknabbert" - es fehlen dort ein paar Knoten. Dann sprechen wir von einem fast vollständigen binären Baum. Die folgende Abbildung zeigt einen fast vollständigen binären Baum.
Bei (fast) vollständigen binären Bäumen stehen die Anzahl der Knoten und die Tiefe in engem Zusammenhang (siehe Übungsaufgabe).
Fast vollständige binäre Bäume spielen beispielsweise beim Sortierverfahren Heapsort eine Rolle.