Bucle (teoría de grafos)

En teoría de grafos, un bucle (también llamado loop, del inglés) es una arista que conecta un vértice consigo mismo. Un gráfico simple no contiene bucles.

Según el contexto, un grafo o multigrafo puede definirse para permitir o no la presencia de bucles (a menudo junto con permitir o no permitir múltiples aristas entre los mismos vértices):

• Cuando los gráficos se definen para permitir bucles y múltiples aristas, un gráfico sin bucles o múltiples aristas a menudo se distingue de otros gráficos llamándolo gráfico simple.
• Cuando los gráficos se definen para no permitir bucles y múltiples bordes, un gráfico que tiene bucles o múltiples bordes a menudo se distingue de los gráficos que satisfacen estas restricciones llamándolo multigrafo o seudógrafo.

En un gráfico con un vértice, todos los bordes deben ser bucles. Tal gráfico se llama ramo.

La licenciatura

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 dejando que cada conexión del borde 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 del borde, lo que suma dos, no uno, al grado.

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