Graphen
Graphen kann man sich als eine Menge von Punkten vorstellen, die durch Linien miteinander verbunden sind. Sehr viele statische und dynamische Strukturen der realen Welt lassen sich mithilfe von Graphen abbilden. Dazu gehören Straßenverbindungen, Kommunikations- und Rechnernetze und Schaltpläne. Im Modul Formale Systeme sind uns Graphen ebenso bereits begegnet, als Darstellungsform von endlichen Automaten.
Abbildung von Stadtteilen und Brücken als Graph
Darstellungsweise
Die Punkten von Graphen werden auch Knoten genannt. Die Linien, die die Knoten miteinander verbinden, bezeichnet man als Kanten.
Je nachdem, ob die Kanten eine Richtung haben, sprechen wir von gerichteten oder von ungerichteten Graphen.
gerichtet
ungerichtet
Definition
Ein allgemeiner, ungerichteter Graph besteht aus
- einer Menge \(K\) von Knoten und
- einer Menge \(E\) von Kanten.
Jeder Kante \(e(u, v) ∈ E\) ist ein Paar von Knoten \((u, v)\) mit \(u, v ∈ K\) zugeordnet. Die beiden zu einer Kante \(e(u, v)\) gehörenden Knoten \(u\) und \(v\) werden als Endknoten der Kante \(e(u, v)\) bezeichnet. Die beiden Endknoten einer Kante sind benachbart.
Meist wird den Knoten eine Bezeichnung oder eine Information zugeordnet.