Vzdálenost (teorie grafů) - Distance (graph theory)

V matematickém poli teorie grafů je vzdálenost mezi dvěma vrcholy v grafu počtem hran v nejkratší cestě (nazývané také graf geodetické ), které je spojují. Toto je také známé jako geodetická vzdálenost nebo vzdálenost nejkratší cesty . Všimněte si, že mezi dvěma vrcholy může být více než jedna nejkratší cesta. Pokud neexistuje cesta spojující dva vrcholy, tj. Pokud patří k různým spojeným komponentám , pak je vzdálenost obvykle definována jako nekonečná.

V případě směrovaného grafu je vzdálenost mezi dvěma vrcholy a definována jako délka nejkratší směrované cesty od do do skládající se z oblouků za předpokladu, že existuje alespoň jedna taková cesta. Všimněte si, že na rozdíl od případu neorientovaných grafů se nemusí nutně shodovat s- je to tedy jen kvazi metrika a může se stát, že jeden je definován, zatímco druhý ne. ${\ Displaystyle d (u, v)}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle v}$${\ Displaystyle d (u, v)}$${\ Displaystyle d (v, u)}$

Související pojmy

Metrický prostor je definován přes sadu bodů, pokud jde o vzdálenost v grafu definovaného nad sadě se nazývá graf metriky . Sada vrcholů (neorientovaného grafu) a funkce vzdálenosti tvoří metrický prostor právě tehdy, je -li graf spojen .

Excentricita z vrcholu je největší vzdálenost mezi a jakékoli další vrchol; v symbolech, tj . V grafu lze uvažovat o tom, jak daleko je uzel od uzlu, který je od něj nejvzdálenější. ${\ Displaystyle \ epsilon (v)}$${\ displaystyle v}$${\ displaystyle v}$${\ Displaystyle \ epsilon (v) = \ max _ {u \ v V} d (v, u)}$

Poloměr grafu je minimální výstřednost každém vrcholu, nebo v symboly . ${\ displaystyle r}$${\ Displaystyle r = \ min _ {v \ in V} \ epsilon (v) = \ min _ {v \ in V} \ max _ {u \ in V} d (v, u)}$

Průměr grafu je maximální výstřednost každém vrcholu v grafu. To je největší vzdálenost mezi jakoukoli dvojicí vrcholů nebo alternativně . Chcete -li zjistit průměr grafu, nejprve najděte nejkratší cestu mezi každou dvojicí vrcholů . Největší délka kterékoli z těchto cest je průměr grafu. ${\ displaystyle d}$${\ displaystyle d}$${\ Displaystyle d = \ max _ {v \ in V} \ epsilon (v) = \ max _ {v \ in V} \ max _ {u \ in V} d (v, u)}$

Centrální vrchol v grafu o poloměru , je ten, jehož excentricita je to jest, vrchol, který dosahuje poloměr, nebo ekvivalentně, vrchol tak, že . ${\ displaystyle r}$${\ displaystyle r}$${\ displaystyle v}$${\ Displaystyle \ epsilon (v) = r}$

Periferní vrchol v grafu průměr je takový, který je vzdálenost od nějakého jiného vrcholu-to znamená, že vrchol, který dosahuje průměr. Formálně je periferní, pokud . ${\ displaystyle d}$${\ displaystyle d}$${\ displaystyle v}$${\ Displaystyle \ epsilon (v) = d}$

Pseudo-periferní vrchol má tu vlastnost, že pro každý vrchol , pokud je tak daleko od je to možné, pak je tak daleko od jak je to možné. Formálně je vrchol u pseudo-periferní, pokud pro každý vrchol v s blokováním . ${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle u}$${\ displaystyle v}$${\ Displaystyle d (u, v) = \ epsilon (u)}$${\ Displaystyle \ epsilon (u) = \ epsilon (v)}$

Partition vrcholů grafu je do podskupin podle jejich vzdáleností od daného výchozího vrcholu se nazývá hladina struktura grafu.

Graf takový, že pro každou dvojici vrcholů existuje jedinečná nejkratší cesta, která je spojuje, se nazývá geodetický graf . Například všechny stromy jsou geodetické.

Tyto vážené nejkratší cesta vzdálenost zobecňuje geodetická vzdálenost k váženými grafů . V tomto případě se předpokládá, že hmotnost okraje představuje jeho délku, nebo pro složité sítě na náklady interakce, a vážená nejkratší cesty vzdálenost je minimální součet hmotností přes všechny cesty spojující a . Další podrobnosti a algoritmy viz problém nejkratší cesty . ${\ Displaystyle d^{W} (u, v)}$${\ displaystyle u}$${\ displaystyle v}$

Algoritmus pro hledání pseudo-periferních vrcholů

Periferní řídké maticové algoritmy často potřebují počáteční vrchol s vysokou excentricitou. Periferní vrchol by byl perfektní, ale často je těžké ho vypočítat. Ve většině případů lze použít pseudo-periferní vrchol. Pseudo-periferní vrchol lze snadno nalézt pomocí následujícího algoritmu:

1. Vyberte vrchol .${\ displaystyle u}$
2. Mezi všemi vrcholy, které jsou od sebe co nejdál , nechme jeden s minimálním stupněm .${\ displaystyle u}$${\ displaystyle v}$
3. Pokud pak nastavíte a opakujete s krokem 2, else je pseudo-periferní vrchol.${\ Displaystyle \ epsilon (v)> \ epsilon (u)}$${\ displaystyle u = v}$${\ displaystyle u}$

Viz také

Poznámky