Graphen

Theorie Icon 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, also Darstellungsform von endlichen Automaten.

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 und von ungerichteten Graphen.

gerichteter Graph gerichteter Graph

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.