Vzdialenosť (teória grafov)

Dĺžku najkratšej cesty medzi vrcholmi ${\displaystyle x}$ a ${\displaystyle y}$ v súvislom grafe ${\displaystyle G}$ (na obrázku), nazývame vzdialenosťou ${\displaystyle x}$ a ${\displaystyle y}$ v ${\displaystyle G}$ a označujeme ${\displaystyle d_{G}(x,y)}$. Napríklad v grafe G (na obrázku) platí: ${\displaystyle d_{G}(6,4)=1}$, ${\displaystyle d_{G}(6,5)=2}$, ${\displaystyle d_{G}(6,1)=3}$. Dá sa dokázať, že funkcia ${\displaystyle d_{G}(x,y)}$ je v súvislom grafe metrika.

• Znám, Š: Kombinatorika a teória grafov. Bratislava, Matematicko-fyzikálna fakulta Univerzity Komenského. 1982, s. 40