Distància (teoria de grafs)

De Viquipèdia
Salta a la navegació Salta a la cerca

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 entre els dos vèrtexs i es defineix com la longitud del camí més curt des de fins a consistent en arcs, sempre que existeixi un camí.[3] En contrast amb els grafs no dirigits, i poden no coincidir o fins i tot pot ser que una de les dues estigui definida i l'altra no.

Referències[modifica]

  1. Bouttier, J.; Di Francesco, P.; Guitter, E «Geodesic distance in planar graphs». Nuclear Physics B, 663, 3, juliol 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.