Vzdialenosť (teória grafov)

Graf G

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

Literatúra

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