Camí (teoria de grafs)

En teoria de grafs, un camí o ruta és una seqüència de vèrtexs dins d'un graf tal que hi ha una aresta entre cada vèrtex i el següent. Es diu que dos vèrtexs estan connectats si existeix un camí que va d'un a un altre, en cas contrari estaran desconnectats. Dos vèrtexs poden estar connectats per diversos camins. El nombre d'arestes dins d'un camí és la seva longitud. Així, els vèrtexs adjacents estan connectats per un camí de longitud 1, i els segons veïns per un camí de longitud 2. Si un camí comença i acaba en el mateix vèrtex s'anomena cicle.

Formalment, un camí és un graf $P$ amb vèrtexs $V(P)=\{v_{0},v_{1},\dots ,v_{l}\}$ i arestes $E(P)=\{\{v_{0},v_{1}\},\{v_{1},v_{2}\},\dots ,\{v_{l-1},v_{l}\}\}$ . La longitud del camí és el nombre d'arestes, $|E(P)|$ .^[1]

Exemples

Un graf és connex si existeixen camins entre cada parell de vèrtexs.
Un graf dirigit és fortament connex si existeixen camins dirigits en un sentit i en l'altre entre cada parell de vèrtexs.
Un camí tal que no hi ha cap aresta que connecti dos vèrtexs no consecutius del camí s'anomena camí induït.
Un camí que inclou tot vèrtex del graf s'anomena camí hamiltonià.
Dos camins són vèrtex-independents si no tenen cap vèrtex intern en comú. De manera semblant, dos camins són aresta-independents si no tenen cap aresta interna en comú. Dos camins vèrtex-independents són automàticament aresta-independents, però el recíproc no és cert.
La distància entre dos vèrtexs d'un graf és la longitud d'un camí mínim entre ells, si existeix; altrament, la distància és infinit.
El diàmetre d'un graf connex és la màxima distància entre parells de vèrtexs del graf.

Càlcul de camins

Existeixen diferents algorismes per tal de trobar el camí més curt o el camí més llarg de grafs, amb la important distinció que el primer problema és computacionalment més senzill que el segon, llevat que P=NP.

L'algorisme de Dijkstra produeix una llista de camins més curts des d'un vèrtex font cap a qualsevol altre vèrtex en grafs dirigits i no dirigits amb pesos no-negatius a les arestes (o sense pesos), mentre que l'algorisme de Bellman-Ford es pot aplicar a grafs dirigits amb pesos negatius a les arestes. L'algorisme de Floyd-Warshall es pot emprar per trobar els camins mínims entre tots els parells de vèrtexs en grafs dirigits amb pesos.

Referències

↑ Bollobás, 1998, p. 4.

Bibliografia

Bollobás, Béla. Modern Graph Theory (en anglès). Springer Science & Business Media, 1998 (Graduate Texts in Mathematics 184). ISBN 9780387984889.
Bondy, John Adrian; Murty, U. S. R.. Graph Theory with Applications. North Holland, 1976, p. 12–21. ISBN 0-444-19451-7 [Consulta: 3 gener 2016]. Arxivat 2010-04-13 a Wayback Machine.
Diestel, Reinhard. Graph Theory. 3a edició. Graduate Texts in Mathematics, vol. 173, Springer-Verlag, 2005, p. 6–9. ISBN 3-540-26182-6.
Gibbons, A. Algorithmic Graph Theory. Cambridge University Press, 1985, p. 5–6. ISBN 0-521-28881-9.
Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander. Paths, Flows, and VLSI-Layout. Algorithms and Combinatorics 9, Springer-Verlag, 1990. ISBN 0-387-52685-4.

Vegeu també

Viccionari

[FOOTNOTEBollobás19984-1] Bollobás, 1998, p. 4.

[1]