Bucle (teoría de grafos)

En teoría de grafos , un bucle (también llamado bucle propio o bucle de seguridad ) es una arista que conecta un vértice consigo mismo. Un grafo simple no contiene bucles.

Dependiendo del contexto, un gráfico o un multigráfico puede definirse de modo que permita o no la presencia de bucles (a menudo junto con permitir o no múltiples aristas entre los mismos vértices):

• Cuando los gráficos se definen de manera que permitan bucles y aristas múltiples, un gráfico sin bucles ni aristas múltiples a menudo se distingue de otros gráficos llamándolo gráfico simple .
• Cuando los gráficos se definen de manera tal que no se permiten bucles ni aristas múltiples, un gráfico que sí tiene bucles o aristas múltiples a menudo se distingue de los gráficos que satisfacen estas restricciones llamándolo multigráfico o pseudográfico .

En un grafo con un vértice, todas las aristas deben ser bucles. Este tipo de grafo se denomina ramo .

Para un gráfico no dirigido , el grado de un vértice es igual al número de vértices adyacentes .

Un caso especial es un bucle, que suma dos al grado. Esto se puede entender haciendo que cada conexión de la arista del bucle cuente como su propio vértice adyacente. En otras palabras, un vértice con un bucle se "ve" a sí mismo como un vértice adyacente desde ambos extremos de la arista, sumando así dos, no uno, al grado.

Para un gráfico dirigido , un bucle agrega uno al grado de entrada y uno al grado de salida .

• Ciclo (teoría de grafos)
• Teoría de grafos
• Glosario de teoría de grafos

• Escalera de Möbius
• Banda de Möbius
• Bucle extraño
• Botella Klein

• Balakrishnan, VK; Graph Theory , McGraw-Hill; 1 edición (1 de febrero de 1997). ISBN  0-07-005489-4 .
• Bollobás, Béla; Teoría de grafos moderna , Springer; 1.ª edición (12 de agosto de 2002). ISBN 0-387-98488-7 . 
• Diestel, Reinhard; Graph Theory , Springer; 2.ª edición (18 de febrero de 2000). ISBN 0-387-98976-5 . 
• Gross, Jonathon L, y Yellen, Jay; Teoría de grafos y sus aplicaciones , CRC Press (30 de diciembre de 1998). ISBN 0-8493-3982-0 . 
• Gross, Jonathon L, y Yellen, Jay; (eds); Manual de teoría de grafos . CRC (29 de diciembre de 2003). ISBN 1-58488-090-2 . 
• Zwillinger, Daniel; Tablas y fórmulas matemáticas estándar del CRC , Chapman & Hall/CRC; 31.ª edición (27 de noviembre de 2002). ISBN 1-58488-291-3 . 

•  Este artículo incorpora material de dominio público de Paul E. Black. "Self loop". Diccionario de algoritmos y estructuras de datos . NIST .