Bucle (teoría de grafos)

Un grafo con un bucle en el vértice 1.

En teoría de grafos, un bucle o loop es una arista que conecta un vértice consigo mismo. Un grafo simple no posee bucles.

Dependiendo del contexto, un grafo o multigrafo puede estar definido o no para permitir en él la presencia de bucles

Grados

Para un grafo no dirigido, el grado de un vértice es igual al número de vértices adyacentes. Sin embargo, si un vértice posee un bucle, debemos añadir dos a su grado. Esto es porque cada conexión de la arista del bucle cuenta como su propio vértice adyacente; o en otras palabras, un vértice con un bucle se ve a sí mismo como un nodo adyacente a ambos vértices finales de la arista.

Para un grafo dirigido, un bucle añade uno al grado de entrada y uno al grado de salida.

Referencias

This article is issued from Wikipedia - version of the Monday, March 11, 2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.