Graphen

Als Modell für das Kürzeste-Wege-Problem (und viele andere Probleme auch) bieten sich Graphen an. Um mit Graphen vertrauter zu werden, denke doch mal über folgende Fragen nach:

• Wie sieht ein Graph aus, der einen U-Bahn-Plan modelliert, in dem alle Bahnhöfe auf dem kürzesten Weg nur eine Station voneinander entfernt sind?
• Gibt es Graphen, in denen keine Knoten benachbart sind?
• Wie sieht ein Graph aus, in dem man den kürzesten Weg besonders gut ablesen kann?
• Zum Knobeln: Kann es einen Graphen geben, der keinen Kreis enthält, aber genauso viele Kanten wie Knoten?

Stelle Dir eigene Fragen und probiere aus!