Vzdálenost (teorie grafů)

Délku nejkratší cesty mezi vrcholy $x$ a $y$ v souvislém grafu $G$ (na obrázku) nazýváme vzdáleností $x$ a $y$ v $G$ a označujeme $d_{G}(x,y)$. Například v grafu G (na obrázku) platí: $d_{G}(6,4)=1$, $d_{G}(6,5)=2$, $d_{G}(6,1)=3$. Dá se dokázat, že funkce $d_{G}(x,y)$ je v souvislém grafu metrikou.

Graf G

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Vzdialenosť (teória grafov) na slovenské Wikipedii.

Literatura

• ZNÁM, Š., 1982. Kombinatorika a teória grafov. Bratislava: Matematicko-fyzikálna fakulta Univerzity Komenského.