Kleines Nachschlagewerk Informatik
Grundbegriffe
Worum geht es?
Im Folgenden sollen die wichtigsten Grundbegriffe erläutert und die Entwicklung eines Graphen aus einem Anwendungsfall heraus gezeigt werden.
Grundbegriffe
Ein Graph besteht aus Knoten, die durch Kanten verbunden werden. So kann man sich Städte als Knoten, die sie verbindenden Straßen als Kanten vorstellen.

Haben diese Kanten eine Richtung, spricht man von einem gerichteten Graph. Vorstellbar ist eine gerichtete Kante beispielsweise als Einbahnstraße.

Das Bild eines Graphen sagt nichts über Entfernungen aus. Liegen zwei Knoten weit auseinander, darf man nicht auf eine hohe Entfernung z.B. bei Städten schließen. Entfernungen werden den Kanten direkt zugewiesen. Man spricht dann von einem gewichteten Graphen.





Das Bild zeigt einen einfachen Graphen mit gewichteten bzw. ungewichteten und gerichteten bzw. ungerichteten Kanten.
Historisches
Entstanden ist - so will es die Legende - die Graphentheorie aus dem Königsberger Brückenproblem. Königsberg besitzt sieben große Brücken, welche die Teile der Stadt verbinden. Die Frage ist nun, kann man einen Weg finden, so dass man alle Brücken nur einmal überquert?