Camí (teoria de grafs)

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

En teoria de grafs, hom denomina camí o ruta, a 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'.

Vegeu també[modifica | modifica el codi]