Die Graphentheorie ist ein Teilgebiet der diskreten Mathematik. Kernelement dabei sind Graphen, insbesondere deren Eigenschaften und Beziehungen zueinander. Anwendungsbereiche von Graphen liegen dabei hauptsächlich im Modellieren von verschiedenen Systemen aus beispielsweise den Bereichen der Biologie, Physik oder Informationstechnik. In der Graphentheorie wird die Struktur eines Graphen untersucht. In der Informatik hat die Graphentheorie eine hervorgehobene Bedeutung, da viele algorithmische Probleme wie das School-Choice-Problem mit Graphen modelliert und mithilfe der Graphentheorie gelöst werden können.
Definition
Ein Graph besteht aus einer Menge von Knoten und einer Menge von Knotenpaaren, welche als Kanten bezeichnet werden. Die Notation für einen Graphen lautet . und stehen dabei für edges und vertices, also die englischen Begriffe für Kanten und Knoten. Eine Kante {, } verbindet die Knoten und .
Beispiel:
Der Graph aus diesem Beispiel hat fünf Knoten und vier Kanten. Die Knotenmenge in diesem Beispiel ist und die Kantenmenge . Es wird zwischen gerichteten und ungerichteten Graphen unterschieden. Bei gerichteten Graphen zeigen die Kanten eine Richtung an. Im obigen Beispiel wird also ein ungerichteter Graph gezeigt.
Im Folgenden werden einige wichtige Eigenschaften von Graphen erklärt.
Inzidenz und Adjazenz beschreiben Beziehungen zwischen Knoten und Kanten in einem ungerichteten Graphen.
Definition
Sei ein ungerichteter Graph. Ein Knoten ist inzident zu einer Kante , falls gilt.
Definition
Sei ein ungerichteter Graph. Zwei Knoten und heißen adjazent oder benachbart zueinander, falls eine Kante {, } existiert. Zudem heißen zwei Kanten adjazent zueinander, wenn beide inzident zu einem benachbarten Knoten sind.
Beispiel:
Durch die rot gefärbte Kante sind die beiden Knoten und adjazent zueinander. Die Knoten und sind jeweils inzident zu der gefärbten Kante, da diese von den jeweiligen Knoten berührt wird.
Definition
Ein Graph heißt vollständig, falls alle Knoten durch eine Kante miteinander verbunden sind.
Beispiel:
In diesem Beispiel sind alle Knoten miteinander verbunden, also ist der Graph vollständig.
Definition
Ein Graph heißt k-regulär, falls alle seine Knoten inzidente Kanten haben. In einem regulären Graphen haben also alle Knoten die gleiche Anzahl an inzidenten Kanten.
Beispiel:
Der Graph aus diesem Beispiel ist ein zwei-regulärer Graph, allerdings kein vollständiger Graph.
Definition
Ein Weg ist ein nicht leerer Graph mit den Knoten , wobei jeder Knoten adjazent zu seinem Nachfolger ist und den Kanten . Ein Weg heißt elementar, wenn jeder Knoten nur einmal vorkommt.
Definition
Ein Kreis in einem Graphen ist eine Folge von Knoten , falls gilt. Ein Kreis heißt elementar, falls jeder Knoten bis auf und nur einmal vorkommt.
Ein Kreis und ein Weg in einem Graphen.
Definition
Ein Graph heißt bipartit, falls seine Knotenmenge in zwei disjunkte Teilmengen und aufgeteilt werden kann, sodass keine Knoten innerhalb einer Teilmenge durch Kanten miteinander verbunden sind. Man schreibt auch .
Beispiel:
Dieses Beispiel zeigt einen bipartiten Graphen. Wichtig ist hierbei, dass es keine Kanten gibt, die Knoten innerhalb der gleichen Teilmenge miteinander verbinden. Einige Sätze, Probleme und Algorithmen beschäftigen sich ausschließlich mit bipartiten Graphen. Hierzu gehören z.B. der Satz von Hall, das School-Choice-Problem und der Boston Algorithmus.