CICLO DE EULER
Un ciclo euleriano es aquel camino que recorre todos los vértices (nodos) de un grafo pasando una y sólo una vez por cada arco (arista) del grafo, siendo condición necesaria que regrese al vértice inicial de salida (ciclo = camino en un grafo donde coinciden vértice inicial o de salida y vértice final o meta). Una definición más formal lo define como: "aquel ciclo que contiene todas las aristas de un grafo solamente una vez".
En la imagen, c= {1,2,3,4,6,3,5,4,1} es un ciclo euleriano, luego es un grafo euleriano.Un grafo es una representación, un modelo, compuesto por un número determinado de vértices (nodos) y un número de arcos (aristas) que los relacionan, cada arista o arco tiene la capacidad de relacionar dos nodos. La palabra ciclo se emplea en teoría de grafos para indicar un camino cerrado en un grafo, es decir, en que el nodo de inicio y el nodo final son el mismo, como contrapartida un camino hamiltoniano es un camino que recorre todos los vértices de un grafo sin pasar dos veces por el mismo vértice. Si el camino es cerrado se dice un ciclo hamiltoniano.
Si un grafo admite un ciclo euleriano, se denomina grafo euleriano.
Determina el ciclo de Euler en la siguiente figura:
¿Para que es útil?
en la vida diaria lo usamos muy frecuentemente, cuando queremos visitar todos nuestros amigos y al final volver a la casa, o cuando estamos en un museo, queremos recorrer todas las salas y volver a salir por la misma entrada. es mas que nada para analizar todo el camino, y ver si hay algun error y mejorarlo.
Entonces, lo que hace este algoritmo es visitar todos los nodos pasando por TODAS las aristas? y llegando siempre al nodo inicial, si mal no estoy eso es lo que entendi. Si estoy mal podrias agregar algo porfavor gracias :D
ResponderEliminarsegun entendi yo en el ciclo de euler se tiene que pasar por todas las aristas, que no importa que se repitan los vértices, siempre y cuando sean visitadas todas las aristas
ResponderEliminarBueno me parece muy completo el tema que nos presentas, creo que es importante señalar las propiedades que presentan los ciclos de euler para complemenatar un poco mas la información.
ResponderEliminarUn grafo conexo y no dirigido se dice que es euleriano si cada vértice tiene un grado par.
Un grafo no dirigido es euleriano si es conexo y si se puede descomponer en uno con los vértices disjuntos.
Si un grafo no dirigido G es euleriano entonces su gráfo-línea L(G) se dice que es también euleriano.
Un grafo dirigido es euleriano si es conexo y cada vértice tiene grados internos iguales a los externos.
Un grafo no dirigido se dice que es susceptible de ser recorrido (en inglés: traversable) si es conexo y al menos dos vértices en el grafo tienen grado impar.
Esta muy bien explicado el tema y con respecto a los otros comentarios en el ciclo de euler si se deben recorrer todas las aristas, para que no se repitan los caminos al volver al inicio el número de vertices que inciden en cada punto debe ser par ( esta condición es necesaria para entrar y salir de cada punto, y para regresar al punto de partida, por caminos distintos en todo momento).
ResponderEliminarque parecido tiene este ciclo de euler con el ciclo de hamilton???
ResponderEliminarSon muy parecidos estos dos ciclos pero la diferencia que existe es que en el ciclo de Hamilton no se conoce ningun algoritmo eficiente para resolverlo en tiempo polinomial, ya que el ciclo hamiltoniano pertenece a los problemas NP-completos, en su solucion requiere basicamente evaluar todas las posibilidades, dando lugar a un orden de complejidad exponencial o factorial. Aunque se parescan es un poco mas dificil el hamiltoniano
ResponderEliminar