V matematické oblasti teorie grafů je vzdálenost mezi dvěma vrcholy v grafu počet hran v nejkratší cestě, která je spojuje. To je také známé jako geodetická vzdálenost.
Existuje řada dalších měření definovaných z hlediska vzdálenosti:
Excentricita vrcholu je největší vzdálenost mezi a jakýmkoli jiným vrcholem.
Poloměr grafu je minimální excentricita jakéhokoli vrcholu.
Průměr grafu je maximální excentricita jakéhokoli vrcholu v grafu. To znamená, že je to největší vzdálenost mezi jakýmikoliv dvěma vrcholy. Periferní vrchol v grafu o průměru je ten, který je vzdálenost od nějakého jiného vrcholu – to znamená vrcholu, který dosahuje průměru.
A pseudo-periferní vrchol má vlastnost, že pro každý vrchol , Pokud je tak daleko od jak je to možné, pak je tak daleko od jak je to možné. Formálně, pokud vzdálenost od do rovná excentricita , Pak se rovná excentricita .
Algoritmus pro hledání pseudo-periferních vrcholů
Často periferní řídké maticové algoritmy 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 pseudoperiferní vrchol. Pseudo-periferní vrchol lze snadno nalézt s následujícím algoritmem: