Camí (teoria de grafs)

De Viquipèdia
Dreceres ràpides: navegació, cerca
Un graf hipercub que mostra un camí hamiltonià (en vermell) i un camí induït màxim (en negre gruixut)

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[modifica | modifica el codi]

  • 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[modifica | modifica el codi]

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[modifica | modifica el codi]

  1. Bollobás, 1998, p. 4.

Bibliografia[modifica | modifica el codi]

Vegeu també[modifica | modifica el codi]