Bucle (teoria de grafs)

De Viquipèdia
Dreceres ràpides: navegació, cerca
Un graf amb un bucle en el vèrtex 1.

En teoria de grafs, un bucle o loop és una aresta que connecta un vèrtex amb si mateix. Un graf simple no té bucles.

Depenent del context, un graf o multigraf pot estar definit o no per permetre-hi la presència de bucles.

Graus[modifica | modifica el codi]

Per a un graf no dirigit, el grau d'un vèrtex és igual al nombre de vèrtexs adjacents. No obstant això, si un vèrtex té un bucle, hem d'afegir dues al seu grau. Això és perquè cada connexió de l'aresta del bucle compte com el seu propi vèrtex adjacent, o en altres paraules, un vèrtex amb un bucle es veu a si mateix com un node adjacent a ambdós vèrtexs finals de l'aresta.

Per a un graf dirigit, un bucle afegeix uno al grau d'entrada i uno al grau de sortida.

Referències[modifica | modifica el codi]

  • Balakrishnan, V. K.; Graph Theory , McGraw-Hill; 1 edition (February 1, 1997). ISBN 0-07-005489-4.
  • Bollobas, Bela; Modern Graph Theory , Springer; 1st edition (August 12, 2002). ISBN 0-387-98488-7.
  • Diestel, Reinhard; Graph Theory , Springer; 2nd edition (February 18, 2000). ISBN 0-387-98976-5.
  • Gross, Jonathon L, and Yellen, Jay; Graph Theory and Its Applications , CRC Press (December 30, 1998). ISBN 0-8493-3982-0.
  • Gross, Jonathon L, and Yellen, Jay; (eds); Handbook of Graph Theory . CRC (December 29, 2003). ISBN 1-58488-090-2.
  • ZWILLING, Daniel; CRC Standard Mathematical Tables and Formuleu , Chapman & Hall/CRC; 31st edition (November 27, 2002). ISBN 1-58488-291-3.