Diferencia entre revisiones de «Bucle (teoría de grafos)»

← Ir a diferencia anterior Ir a siguiente diferencia →

Contenido eliminado Contenido añadido

En renglón

Revisión del 07:39 3 abr 2010

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

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.
Zwillinger, Daniel; CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC; 31st edition (November 27, 2002). ISBN 1-58488-291-3.

@@ Línea 7: / Línea 7: @@
 == Grados ==
-Para un [[grafo no dirigido]], el [[grado (teoría de grafos)|grado]] de un vértice es igual al número de [[nodos vecinos|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 no dirigido]], el [[grado (teoría de grafos)|grado]] de un vértice es igual al número de [[vecindad (teoría de grafos)|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 (teoría de grafos)|grado de entrada]] y ''uno'' al [[grado (teoría de grafos)|grado de salida]].