Distància (teoria de grafs)

En teoria de grafs, la distància entre els dos vèrtexs d'un graf és el nombre d'arestes en el camí més curt que els uneix. Això també es coneix com a distància geodèsica.^[1] Hi pot haver més d'un camí més curt entre dos vèrtexs.^[2] Si no hi ha cap camí que uneixi els dos vèrtexs, per exemple perquè pertanyen a diferents components, per convenció es diu que la distància entre ells és infinita.

En el cas d'un graf dirigit la distància ${\displaystyle d(u,v)}$ entre els dos vèrtexs ${\displaystyle u}$ i ${\displaystyle v}$ es defineix com la longitud del camí més curt des de ${\displaystyle u}$ fins a ${\displaystyle v}$ consistent en arcs, sempre que existeixi un camí.^[3] En contrast amb els grafs no dirigits, ${\displaystyle d(u,v)}$ i ${\displaystyle d(v,u)}$ poden no coincidir o fins i tot pot ser que una de les dues estigui definida i l'altra no.

Referències

1. Bouttier, J.; Di Francesco, P.; Guitter, E «Geodesic distance in planar graphs». Nuclear Physics B, 663, 3, 7-2003, pàg. 535–567. DOI: 10.1016/S0550-3213(03)00355-9. «By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces»
2. Weisstein, Eric W. «Graph Geodesic». MathWorld--A Wolfram Web Resource. Wolfram Research. [Consulta: 1r maig 2015].
3. Harary, Frank. Graph Theory. Addison-Wesley, 1969. ISBN 978-0201410334.

Viccionari