Ciclos

Solo disponible en BuenasTareas
  • Páginas : 2 (344 palabras )
  • Descarga(s) : 0
  • Publicado : 16 de diciembre de 2010
Leer documento completo
Vista previa del texto
¿Qué es el ciclo?
Un ciclo es un tipo especial de permutación que fija cierto número de elementos (quizás ninguno) mientras que mueve cíclicamente el resto. En caso de no fijar ningún elemento lodenominaríamos permutación cíclica.
Más concretamente, si un ciclo afecta a un elemento x cualquiera del conjunto, al aplicar dicho ciclo reiteradamente todos los elementos afectados por elreordenamiento pasarán por la posición de x en algún momento. Y de forma recíproca, el elemento x pasará por todas las posiciones de todos los elementos afectados por la permutación.
Los ciclos son tipos depermutación especialmente importantes, pues pueden usarse como piezas básicas para construir cualquier otra permutación

Ciclos Eureleanos
Se denomina grafo euleriano, a un grafo conexo G que tieneuna cola cerrada que
incluye todas las aristas de G.

Teorema de Euler: Un grafo es euleriano si y sólo si cada vértice es de grado
par. Si tiene exactamente dos vértices impares es recorrible (lacola no será cerrada) y se
llama semieuleriano.

A continuación se muestran ejemplos de grafos no eulerianos, semieulerianos y
eulerianos respectivamente.
Trayectoria de Euler: es un camino quepasa por todo arco solo una vez
Circuito de Euler: es un ciclo que pasa por todo arco solo una vez
La solución al problema de existencia de ciclos de Euler se puede establecer mediante el grado de unvértice (es el numero de arcos que tiene ese vértice como extremo).
Teorema 1: Si una grafica G tiene un vértice de grado impar, entonces no puede existir un circuito de Euler en G.
Si G es unagrafica conexa y todos los vértices tienen grado par, entonces existe un circuito de Euler en G.
Teorema 2: Si una grafica G tiene mas de dos vértices de grado impar, entonces no puede existir unatrayectoria de Euler en G.
Si G es conexa y tiene exactamente dos vértices de grado impar, entonces existe una trayectoria de Euler en G. Cualquier trayectoria de Euler debe comenzar en un vértice de...
tracking img