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

V matematický pole teorie grafů, vzdálenost mezi dvěma vrcholy v graf je počet hran v a nejkratší cesta (také nazývaný a graf geodetický) jejich připojení. Toto je také známé jako geodetická vzdálenost.^[1] Všimněte si, že mezi dvěma vrcholy může být více než jedna nejkratší cesta.^[2] Pokud neexistuje žádná cesta spojující dva vrcholy, tj. Pokud patří k různým připojené komponenty, pak je vzdálenost běžně definována jako nekonečná.

V případě a řízený graf vzdálenost ${ displaystyle d (u, v)}$ mezi dvěma vrcholy ${ displaystyle u}$ a ${ displaystyle v}$ je definována jako délka nejkratší směrované cesty od ${ displaystyle u}$ na ${ displaystyle v}$ skládající se z oblouků, pokud existuje alespoň jedna taková cesta.^[3] Všimněte si, že na rozdíl od neorientovaných grafů ${ displaystyle d (u, v)}$ se nemusí nutně shodovat s ${ displaystyle d (v, u)}$a může se stát, že jeden je definován, zatímco druhý není.

Související pojmy

A metrický prostor definovaný přes množinu bodů z hlediska vzdáleností v grafu definovaném přes množinu se nazývá a metrika grafu.Skupina vrcholů (neorientovaného grafu) a funkce vzdálenosti tvoří metrický prostor, právě když je graf připojeno.

The excentricita ${ displaystyle epsilon (v)}$ vrcholu ${ displaystyle v}$ je největší vzdálenost mezi ${ displaystyle v}$ a jakýkoli jiný vrchol; v symbolech to je ${ displaystyle epsilon (v) = max _ {u ve V} d (v, u)}$. Lze si představit, jak daleko je uzel od nejvzdálenějšího uzlu v grafu.

The poloměr ${ displaystyle r}$ grafu je minimální excentricita jakéhokoli vrcholu nebo v symbolech ${ displaystyle r = min _ {v v V} epsilon (v) = min _ {v ve V} max _ {u ve V} d (v, u)}$.

The průměr ${ displaystyle d}$ grafu je maximální excentricita jakéhokoli vrcholu v grafu. To znamená, ${ displaystyle d}$ je největší vzdálenost mezi jakoukoli dvojicí vrcholů nebo alternativně ${ displaystyle d = max _ {v v V} epsilon (v)}$. Chcete-li zjistit průměr grafu, nejprve najděte nejkratší cesta mezi každou dvojicí vrcholy. Největší délka kterékoli z těchto cest je průměr grafu.

A centrální vrchol v grafu poloměru ${ displaystyle r}$ je ten, jehož výstřednost je ${ displaystyle r}$—To je vrchol, který dosahuje poloměru, nebo ekvivalentně vrchol ${ displaystyle v}$ takhle ${ displaystyle epsilon (v) = r}$.

A periferní vrchol v grafu průměru ${ displaystyle d}$ je ten, který je vzdálenost ${ displaystyle d}$ z nějakého jiného vrcholu - to je vrchol, který dosahuje průměru. Formálně, ${ displaystyle v}$ je periferní, pokud ${ displaystyle epsilon (v) = d}$.

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

The rozdělit vrcholy grafu do podskupin podle jejich vzdáleností od daného počátečního vrcholu se nazývá struktura úrovně grafu.

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

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

Často periferní řídká matice Algoritmy potřebují počáteční vrchol s vysokou výstředností. Periferní vrchol by byl dokonalý, ale je často těžké jej vypočítat. Ve většině případů lze použít pseudo-periferní vrchol. Pseudo-periferní vrchol lze snadno najít pomocí následujícího algoritmu:

1. Vyberte vrchol ${ displaystyle u}$.
2. Mezi všemi vrcholy, které jsou tak daleko od ${ displaystyle u}$ jak je to možné, nechte ${ displaystyle v}$ být jedním s minimem stupeň.
3. Li ${ displaystyle epsilon (v)> epsilon (u)}$ pak nastavit ${ displaystyle u = v}$ a opakujte krok 2, jinak ${ displaystyle u}$ je pseudo-periferní vrchol.

Viz také

Poznámky