Camí (teoria de grafs)

De Viquipèdia
Dreceres ràpides: navegació, cerca

En teoria de grafs, un camí o ruta és una seqüència de vèrtexs dins d'un graf tal que hi hagi una aresta entre cada vèrtex i el següent. Es diu que dos vèrtexs estan connectats si existeix un camí que vagi 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]

Referències[modifica | modifica el codi]

Bibliografia[modifica | modifica el codi]

Vegeu també[modifica | modifica el codi]