Distanz (Graphentheorie) - Distance (graph theory)

Auf dem mathematischen Gebiet der Graphentheorie ist der Abstand zwischen zwei Knoten in einem Graph die Anzahl der Kanten auf einem kürzesten Pfad (auch als geodätischer Graph bezeichnet ), der sie verbindet. Dies wird auch als geodätische Distanz oder kürzeste Pfaddistanz bezeichnet . Beachten Sie, dass es zwischen zwei Scheitelpunkten mehr als einen kürzesten Pfad geben kann. Gibt es keinen Pfad, der die beiden Eckpunkte verbindet, dh gehören sie zu verschiedenen zusammenhängenden Komponenten , dann wird der Abstand konventionell als unendlich definiert.

Bei einem gerichteten Graphen ist der Abstand zwischen zwei Scheitelpunkten und definiert als die Länge eines kürzesten gerichteten Weges von bis aus Bögen, sofern mindestens ein solcher Weg existiert. Beachten Sie, dass im Gegensatz zu ungerichteten Graphen nicht unbedingt mit — also nur eine Quasi-Metrik zusammenfällt , und es kann sein, dass einer definiert ist, der andere nicht. ${\displaystyle d(u,v)}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle d(u,v)}$${\displaystyle d(v,u)}$

Verwandte konzepte

Ein metrischer Raum , der über eine Menge von Punkten in Bezug auf Abstände in einem über der Menge definierten Graphen definiert ist, wird als Graphenmetrik bezeichnet . Der Artikulationssatz (ein ungerichteten Graphen) und die Abstandsfunktion einen metrischen Raum bilden, wenn und nur wenn der Graph verbunden .

Die Exzentrizität eines Scheitelpunkts ist der größte Abstand zwischen einem anderen Scheitelpunkt; in Symbolen das ist . Man kann sich vorstellen, wie weit ein Knoten von dem am weitesten entfernten Knoten im Graphen entfernt ist. ${\displaystyle \epsilon (v)}$${\displaystyle v}$${\displaystyle v}$${\displaystyle \epsilon(v)=\max_{u\in V}d(v,u)}$

Der Radius eines Graphen ist die minimale Exzentrizität eines Scheitelpunkts oder, in Symbolen, . ${\displaystyle r}$${\displaystyle r=\min_{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u)}$

Der Durchmesser eines Graphen ist die maximale Exzentrizität eines beliebigen Scheitelpunkts im Graphen. Das heißt, ist der größte Abstand zwischen einem Paar von Scheitelpunkten oder alternativ . Um den Durchmesser eines Graphen zu bestimmen, finden Sie zuerst den kürzesten Weg zwischen jedem Knotenpaar . Die größte Länge eines dieser Pfade ist der Durchmesser des Graphen. ${\displaystyle d}$${\displaystyle d}$${\displaystyle d=\max_{v\in V}\epsilon (v)=\max _{v\in V}\max _{u\in V}d(v,u)}$

Eine zentrale Ecke in einem Radiusgraphen ist eine, deren Exzentrizität ist – das heißt eine Ecke, die den Radius erreicht, oder äquivalent eine Ecke, so dass . ${\displaystyle r}$${\displaystyle r}$${\displaystyle v}$${\displaystyle \epsilon(v)=r}$

Ein peripherer Scheitelpunkt in einem Durchmesserdiagramm ist ein Scheitelpunkt, der von einem anderen Scheitelpunkt entfernt ist – das heißt, ein Scheitelpunkt, der den Durchmesser erreicht. Formal ist peripher, wenn . ${\displaystyle d}$${\displaystyle d}$${\displaystyle v}$${\displaystyle \epsilon(v)=d}$

Ein pseudoperipherer Knoten hat die Eigenschaft, dass für jeden Knoten , wenn er so weit wie möglich entfernt ist, dann so weit wie möglich entfernt ist. Formal ist eine Ecke u pseudoperipher, wenn für jede Ecke v mit gilt . ${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle u}$${\displaystyle v}$${\displaystyle d(u,v)=\epsilon(u)}$${\displaystyle \epsilon (u)=\epsilon (v)}$

Die Aufteilung der Scheitelpunkte eines Graphen in Teilmengen durch ihre Abstände von einem gegebenen Startscheitelpunkt wird als Ebenenstruktur des Graphen bezeichnet.

Ein Graph, bei dem es für jedes Knotenpaar einen eindeutigen kürzesten Weg gibt, der sie verbindet, wird als geodätischer Graph bezeichnet . Alle Bäume sind beispielsweise geodätisch.

Die gewichtete Shortest-Path-Distanz verallgemeinert die geodätische Distanz zu gewichteten Graphen . In diesem Fall wird angenommen, dass das Gewicht einer Kante ihre Länge oder bei komplexen Netzwerken die Kosten der Interaktion darstellt und die gewichtete kürzeste Wegstrecke die minimale Summe der Gewichte über alle Wege ist, die und verbinden . Siehe das Kürzeste-Weg-Problem für weitere Details und Algorithmen. ${\displaystyle d^{W}(u,v)}$${\displaystyle u}$${\displaystyle v}$

Algorithmus zum Finden von pseudo-peripheren Vertices

Periphere Sparse-Matrix- Algorithmen benötigen oft einen Startknoten mit einer hohen Exzentrizität. Ein peripherer Scheitel wäre perfekt, ist aber oft schwer zu berechnen. In den meisten Fällen kann ein pseudo-peripherer Scheitelpunkt verwendet werden. Ein pseudo-peripherer Vertex kann leicht mit dem folgenden Algorithmus gefunden werden:

1. Wählen Sie einen Scheitelpunkt aus .${\displaystyle u}$
2. Unter allen Knoten, die möglichst weit entfernt sind , sei einer mit minimalem Grad .${\displaystyle u}$${\displaystyle v}$
3. Wenn dann gesetzt und mit Schritt 2 wiederholt, ist sonst ein pseudo-peripherer Scheitelpunkt.${\displaystyle \epsilon (v)>\epsilon (u)}$${\displaystyle u=v}$${\displaystyle u}$

Siehe auch

Anmerkungen