Infos Home | Impressum | Original Artikel & Autoren Liste

Distanz (Graphentheorie)

Als Distanz oder Abstand zweier Knoten in einem Graph bezeichnet man die Länge eines kürzesten Pfadeses zwischen diesen. Falls ein solcher Pfad nicht existiert, so setzt man den Abstand auf unendlich. Der Abstand eines Knoten zu sich selbst ist Null.

Man beachte, dass in gerichteten Graphen der Abstand von der Richtung des Pfades abhängt. Dabei kann es sogar vorkommen, dass ein endlicher Abstand nur in eine Richtung existiert.

Die Ermittlung des kürzesten Abstands zweier Knoten ist zum Beispiel für Routenplaner wichtig. Er lässt sich auf einfache Weise mit dem Algorithmus von Dijkstra berechnen.

Aus den paarweisen Distanzen aller Knoten eines Graphen lässt sich der Distanzgraph konstruieren.

Beispiele

Ein Beispiel für den Abstand in Graphen ist der Abstand zweier Personen in Sozialen Netzwerken. Dabei werden die Personen als Knoten repräsentiert, zwischen denen jeweils eine Kante existiert wenn sie sie einander kennen oder durch eine andere Eigenschaft miteinander verbunden sind (siehe dazu auch Small World Phänomen und Erdös-Zahl).

Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste").
Der Text steht unter der GNU Freie Dokumentation Lizenz.

Webtipps: Branchenbuch Deutschland