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