Bucle (teoria de grafs)
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]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 de sumar 2 al grau. Això és perquè cada connexió de l'aresta del bucle compta 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 des dels dos extrems de l'aresta.
Per a un graf dirigit, un bucle suma 1 al grau d'entrada i 1 al grau de sortida.
Bibliografia
[modifica]- 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.
