Graphen (Wege 2 )

 

Joes Problem ist ein typisches Wege-Problem auf einem Graphen.

der USA-Graph

	Die Nachbarschaften der Staaten der USA ...
	...werden durch einen Graphen beschrieben.
	Big Bad Joe muss vom linken blauen Knoten zum rechten.

 

Anschaulich besteht ein Graph aus Knoten und aus Kanten, welche jeweils zwei Knoten verbinden.

Unser Beispiel 

Im USA-Graph gilt:

• Knoten: die 48 Staaten der USA (ohne Alaska und Hawaii)
• Kanten: Zwei Knoten sind durch eine Kante verbunden, wenn die zugehörigen Staaten eine gemeinsame Grenze haben.

 

Joes Problem lautet also:

Finde einen Weg von Kalifornien nach Pennsylvania mit möglichst wenig Kanten.

Dies ist eine Abstandsaufgabe für den USA-Graph.

Abstands-
aufgabe 

Gegeben: Ein Graph und zwei Knoten des Graphen.
Gesucht: Ein Weg mit möglichst wenig Kanten, der die beiden Knoten verbindet. Die Anzahl der Kanten dieses Weges ist der Abstand der beiden Knoten.

eine Lösung für Joe 

Bewege die Maus über das Bild.

Gibt es noch andere Lösungen?

Seite 2/12 
 

usa0

usa1

usa2