Odległość (teoria grafów) - Distance (graph theory)

W matematycznej dziedzinie teorii wykres The odległość między dwoma wierzchołkami w wykresie jest liczba krawędzi w najkrótszej ścieżce (zwany również geodezyjnej wykres ) ich połączeniem. Jest to również znane jako odległość geodezyjna lub odległość najkrótszej ścieżki . Zauważ, że może istnieć więcej niż jedna najkrótsza ścieżka między dwoma wierzchołkami. Jeśli nie ma ścieżki łączącej dwa wierzchołki, tj. jeśli należą one do różnych połączonych składowych , wtedy konwencjonalnie odległość jest definiowana jako nieskończona.

W przypadku wystąpienia skierowanej wykresie odległość między dwoma wierzchołkami i jest definiowana jako długość najkrótszego kierunek ruchu ścieżki od celu składa się z łuków, przy czym co najmniej jedna taka ścieżka istnieje. Zauważ, że w przeciwieństwie do przypadku grafów nieskierowanych, niekoniecznie pokrywa się z —więc jest to tylko quasi-metryka i może być tak, że jeden jest zdefiniowany, a drugi nie. ${\displaystyle d(u,v)}$${\ Displaystyle u}$${\displaystyle v}$${\ Displaystyle u}$${\displaystyle v}$${\displaystyle d(u,v)}$${\displaystyle d(v,u)}$

Pojęcia pokrewne

Przestrzenią metryczną zdefiniowana przez zbiór punktów pod względem odległości w postaci wykresu zdefiniowany przez zestaw nazywa się wykres metryczny . Zbiór wierzchołków (grafu nieskierowanego) i funkcja odległości tworzą przestrzeń metryczną wtedy i tylko wtedy, gdy graf jest połączony .

Mimośród od wierzchołka jest największa odległość między i każdy inny wierzchołek; w symbolach, czyli . Można to traktować jako odległość węzła od węzła najbardziej oddalonego od niego na wykresie. ${\ Displaystyle \ epsilon (v)}$${\displaystyle v}$${\displaystyle v}$${\ Displaystyle \ epsilon (v) = \ max _ {u \ w V} d (v, u)}$

Promień wykresu jest minimalna mimośród każdym wierzchołku lub w symboli . ${\ Displaystyle r}$${\ Displaystyle r = \ min _ {v \ w V} \ epsilon (v) = \ min _ {v \ w V} \ max _ {u \ w V} d (v, u)}$

Średnica wykresu jest maksymalna mimośrodowość każdym wierzchołku na wykresie. Oznacza to, że jest to największa odległość między dowolną parą wierzchołków lub alternatywnie . Aby znaleźć średnicę wykresu, najpierw znajdź najkrótszą ścieżkę między każdą parą wierzchołków . Największa długość którejkolwiek z tych ścieżek to średnica wykresu. ${\displaystyle d}$${\displaystyle d}$${\ Displaystyle d = \ max _ {v \ w V} \ epsilon (v) = \ max _ {v \ w V} \ max _ {u \ w V} d (v, u)}$

Centralny wierzchołek na wykresie o promieniu jest której mimośród jest -to jest wierzchołek promienia, który osiąga lub równoważnie wierzchołek , tak że . ${\ Displaystyle r}$${\ Displaystyle r}$${\displaystyle v}$${\ Displaystyle \ epsilon (v) = r}$

Wierzchołka obwodowych na wykresie średnicy jest w niewielkiej odległości od innego wierzchołka, to znaczy wierzchołka, który osiąga średnicę. Formalnie jest peryferyjny, jeśli . ${\displaystyle d}$${\displaystyle d}$${\displaystyle v}$${\ Displaystyle \ epsilon (v) = d}$

Pseudo-obwodowy wierzchołek ma tę właściwość, że dla każdego wierzchołka , jeśli jest tak daleko od , jak to możliwe, to jest tak daleko od , jak to możliwe. Formalnie wierzchołek u jest pseudo-peryferyjny, jeśli dla każdego wierzchołka v z uchwytami . ${\displaystyle v}$${\ Displaystyle u}$${\displaystyle v}$${\ Displaystyle u}$${\ Displaystyle u}$${\displaystyle v}$${\ Displaystyle d (u, v) = \ epsilon (u)}$${\ Displaystyle \ epsilon (u) = \ epsilon (v)}$

Przegroda wierzchołków wykres jest na podzbiory ich odległości od danego wierzchołka wyjściowego nazywany poziomie struktury wykresu.

Graf taki, że dla każdej pary wierzchołków istnieje unikalna najkrótsza droga łącząca je, nazywa się grafem geodezyjnym . Na przykład wszystkie drzewa są geodezyjne.

Te ważone najkrótszej ścieżki odległość Rozpowszechnia geodezyjnej odległość do ważonych wykresach . W tym przypadku przyjmuje się, że masa z krawędzi stanowi jego długości lub, w przypadku złożonych sieci o koszty interakcji i ważonej odległości najkrótszej ścieżki jest sumą najmniej obciążników we wszystkich ścieżek łączenia i . Zobacz problem z najkrótszą ścieżką, aby uzyskać więcej szczegółów i algorytmów. ${\ Displaystyle d ^ {W} (u, v)}$${\ Displaystyle u}$${\displaystyle v}$

Algorytm znajdowania wierzchołków pseudoperyferyjnych

Często algorytmy peryferyjnych macierzy rzadkich wymagają wierzchołka początkowego o dużej mimośrodowości. Peryferyjny wierzchołek byłby idealny, ale często trudno go obliczyć. W większości przypadków można użyć wierzchołka pseudoperyferyjnego. Wierzchołek pseudoperyferyjny można łatwo znaleźć za pomocą następującego algorytmu:

1. Wybierz wierzchołek .${\ Displaystyle u}$
2. Wśród wszystkich wierzchołków, które są jak najdalej od siebie , niech będzie jeden z minimalnym stopniem .${\ Displaystyle u}$${\displaystyle v}$
3. Jeśli następnie ustawisz i powtórzysz krok 2, inaczej jest wierzchołkiem pseudo-peryferyjnym.${\ Displaystyle \ epsilon (v)> \ epsilon (u)}$${\displaystyle u=v}$${\ Displaystyle u}$

Zobacz też

Uwagi