Vzdálenost (teorie grafů)

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

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

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

Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.