Startseite    
MathematikPoolNRW Projekt Hintergründe Kontakt


Einige Begriffe der Graphentheorie

Als Abstraktion eines Verkehrsnetzes, das aus Bahnhöfen, Städten oder Kreuzungen und Gleis- oder Straßenverbindungen besteht, verwenden wir Graphen.

Ein gerichteter Graph besteht aus

  • einer (endlichen) Menge V von Knoten und
  • einer (endlichen) Menge E von Kanten,
die je zwei Knoten miteinander verbinden. Wir können daher E mit einer Teilmenge { (v,w) aus V } identifizieren. Zusätzlich seien nichtnegative ''Entfernungen'' c(v,w) >= 0  gegeben und ein Startknoten s aus V ausgezeichnet.

Wir veranschaulichen uns Graphen, indem wir die Knoten als kleine Kreise zeichnen und die Kanten (v,w) als Pfeile, die einen Knoten v mit einem Knoten w verbinden.


Beispiel:



Unter einem Weg   P   von einem Knoten   v   zu einem anderen Knoten   w   verstehen wir eine Folge   v0, v1, ... , vk   von Knoten, so daß   v0 = v,  vk = w   und   (vi, vi+1) Kanten aus   E  sind. Der Weg hat die Länge

c(P) = c(v0,v1) + c(v1, v2) + ... + c(vk-1,vk).


Beispiel:    In dem folgenden Graphen führt der Weg P von Knoten v1 über die Knoten v2 und v3 nach v4.
                  Er hat die Länge
c(P) = 12 + 17 + 7 = 36



Das kürzeste-Weg-Problem besteht darin, Wege kürzester Länge von s zu einem ausgezeichneten Zielknoten t bzw. zu allen anderen Knoten zu bestimmen.