Einführung: Graphentheorie

Dieses Kapitel beschäftigt sich mit der Graphentheorie. Ein Graph besteht aus verschiedenen Knoten, welche ganz oder teilweise miteinander verbunden sind. Die Graphentheorie findet Anwendung z.B. bei der Planung von Verkehrsnetzen, Kommunikationsnetzen oder auch Versorgungsnetzen.

Grundbegriffe der Graphentheorie

Ein Graph besteht aus einer nichtleeren Knotenmenge und einer Pfeil- oder Kantenmenge . Jedem Element aus ist genau ein Knotenpaar aus zugeordnet.

Es handelt sich um einen ungerichteten Graphen, wenn die Elemente nicht geordnet sind. Die Elemente werden dann als Kanten bezeichnet. Ein gerichteter Graph hingegen liegt vor, wenn die Elemente geordnet sind. Die Elemente werden dann als Pfeile bezeichnet.

Der Unterschied zwischen einem ungerichteten Graphen und einem gerichteten Graphen ist die Kanten-bzw. Pfeilmenge . Die Knotenmenge ist für die beiden Graphen gleich. Die Kantenmenge für den ungerichteten Graphen ist . Die Pfeilmenge für den gerichteten Graphen ist .

Ein Pfeil bzw. eine Kante mit gleichem Anfangs- und Endknoten heißt Schlinge.

Besitzen zwei Pfeile bzw. Kanten den gleichen Anfangs-und Endknoten so nennt man diese parallel.

Ein schlichter Graph ist ein Graph ohne Schlinge und ohne parallele Pfeile bzw. Kanten.

Ein Diagraph ist ein schlichter gerichteter Graph mit endlicher Knotenmenge.

In einem ungerichteten Graphen bezeichnet man einen Knoten als Nachfolger eines Knotens , wenn ein Pfeil existiert. Dabei wird die Menge aller Nachfolger eines Knotens mit bezeichnet. In einem gerichteten Graphen heißt ein Knoten Nachbar von Knoten , wenn eine Kante existiert. Dabei wird die Menge aller Nachbarn eines Knotens mit bezeichnet.

In einem gerichteten Graphen wird ein Knoten ohne Vorgänger Quelle genannt und ein Knoten ohne Nachfolger Senke.

In den folgenden Abschnitten werden Verfahren zur Bestimmung kürzester Wege im Graphen aufgezeigt sowie Verfahren zur Bestimmung minimaler Spannbäume und minimaler 1-Bäume.