No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Caminos y ciclos eulerianos

19/40
Recursos

Ya sabes que un camino es una sucesi贸n de v茅rtices y conexiones donde no pasas dos veces por el mismo v茅rtice, y un ciclo es una sucesi贸n de v茅rtices y conexiones donde el nodo de inicio es igual al nodo final.

Pues un Camino Euleriano es aquel camino que recorre todo el grafo sin repetir una conexi贸n, esto se cumplir谩 siempre y cuando un grafo no tenga m谩s de dos v茅rtices con grado impar.

Un Ciclo Euleriano es aquel ciclo que recorre todo el grafo sin repetir una conexi贸n, este se cumplir谩 solo cuando todos los v茅rtices del grafo son grado par.

Aportes 36

Preguntas 2

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

Camino euleriano => https://repl.it/@alvarojmp/eulerian-path

Ciclo euleriano => https://repl.it/@alvarojmp/eulerian-cycle

Hacer clic en Run.

Saludos

En un camino se supone que no se debe de repetir ni v茅rtice ni arista, 驴Por qu茅 en un camino Euleriano s铆 puedo repetir los v茅rtices mas no las aristas?

En el ejemplo del profe:
Ve-Vd-Vc-Va-Vd-Vb-Va-Vb-Ve-Vf
Se repiten los v茅rtices en negrita



Condici贸n para la existencia de un camino euleriano:
No existen m谩s de dos vertices con grado impar, adem谩s el camino debe empezar y terminar en un vertice con grado impar.
Condici贸n para la existencia de un ciclo euleriano:
Todos los vertices tienen grado par, adem谩s, como es un ciclo, empieza y termina en el mismo vertice.

Un profesor completamente confundido e ignorante de este tema. La plataforma deber铆a tener un profesor revisor de cada curso, que pudiera evitar subir este tipo de contenido. Se nota que el profesor se da cuenta cuando se confunde y acelera el paso para salir cuanto antes del tema, se vale en un curso presencial, pero 驴en un curso en l铆nea y que adem谩s tiene costo? La cr铆tica es para que sustituyan la lecci贸n por una que sea correcta.

Caminos y ciclos Eulerianos:
Camino Euleriano: Consiste en un camino que recorra todos los vertices y aristas sin repetir aristas. Para que exista un camino euleriano se debe cumplir que existen como m谩ximo dos vertices de grado impar y debemos empezar por ellos.
Ciclo euleriano: Es un camino euleriano que inicia y termina en el mismo v茅rtice. Para que exista todos los vertices del grafo deben ser pares,

Por lo que estuve viendo de teoria de grafos encontre las siguientes definiciones
Cadena: a toda sucesion finita y alterna de vertices y aristas
Camino: a toda cadena en la que no se repiten ni vertices ni aristas
De aqui se desprende que no existe camino euleriano ya que contradice la definicion de camino anterior.
Por lo tanto lo correcto seria Cadena Euleriana, de esta forma si podemos recorrer todo el grafo pasando por todas sus aristas (lo que implica repetir vertices)

El punto G jejeje

La condici贸n de los caminos Eulerianos, se refiere a poder pasar toda la gr谩fica, sin repetir caminos y ni alzar el l谩piz. Luego el ciclo, cumple con la misma condici贸n, sin embargo, Vi=Vf, osea que solo podemos terminar por d贸nde hemos terminado, pero sin repetir caminos.

para un CICLO EULERIANO, todos los v茅rtices deben SER PARES.

Resumiendo lo anterior
Sea G un grafo conexo entonces

G es euleriano, es decir tiene ciclo euleriano, si solo si todos sus vertices tienen grado par

G tiene cadena euleriana no cerrada si y solo si G tiene exactamente dos vertices de grado impar (que seran los extremos de la cadena)

  • Para que exista un camino euleriano deben existir no m谩s de dos v茅rtices con grado impar. Se debe iniciar y terminar en los v茅rtices de grado impar.
    Para que exista un ciclo euleriano , todos los v茅rtices deben ser par.

Este tema qued贸 un poco suelto les recomiendo ver este video => https://www.youtube.com/watch?v=8MpoO2zA2l4

Para los que no sepan ingl茅s tiene subt铆tulos en espa帽ol

Teorema de Euler:
a. Si un grafo conexo tiene m谩s de dos nodos con grado impar, no existe un camino simple de Euler.

b. Si existen exactamente dos v茅rtices de grado impar, el grafo se puede recorrer, pero el camino ha de empezar en uno de los dos v茅rtices de grado impar y terminar en el otro.

c. Si no existen v茅rtices de grado impar, el grafo se puede recorrer. El camino siempre ser谩 cerrado.

Explicacion de cadena euleriana y grafo euleriano []https://www.youtube.com/watch?v=GYknoMYjxBE

Camino Euleriano: No mas de dos v茅rtices con grado impar. Puedo repetir v茅rtice pero no arista.

Ciclo Euclidiano: Todos los vertices de grado par. Inicio y termino en el mismo v茅rtice sin repetir aristas.

Hay camino euleriano, cuando hay dos y solo dos v茅rtices impar; si hay mas de dos NO HAY CAMINO EULERIANO.

Excelente explicaci贸n.

Tremenda explicaci贸n

Algunas correcciones.

  1. Cuando se habla de Camino Euleriano, se 鈥減ermite鈥 repetir v茅rtices ya que esta condici贸n aplica para Caminos Simples (no repiten ni v茅rtice ni arista). Los camino Eulerianos son un tipo de camino que no son simples, pero que s铆 cumplen con que no recorren m谩s de una vez las aristas.
  2. Un camino Euleriano debe contener exactamente 2 v茅rtices con grado impar. En la clase se dice 鈥淣o m谩s de dos鈥 y es cierto, pero esto incluir铆a el caso de tener un (1) v茅rtice impar, y en ese caso no ser铆a un camino Euleriano. Deben ser exactamente 2.

Este es el teorema:
Sea G un grafo o multigrafo no dirigido. Entonces G tiene un camino de Euler si, y solo si, es conexo y tiene solo dos v茅rtices de grado impar. Diremos que el grafo es semi-Euleriano.

camino : sucesion de vertices o conexiones sin pasar dos veces por el mismo nodo (vertice)
ciclo: inicia y termina en el mismo nodo
camino euleriano: no mas de dos nodos con grado impar, inicia y termina en estos nodos respectivamente
ciclo euleriano: todos los vertices deben tener grado par

Adem谩s de los grafos eulerianos, tambi茅n existen los grafos semieulerianos, que cumplen una condici贸n ligeramente diferente. Un grafo es semieuleriano si tiene exactamente dos v茅rtices de grado impar y el resto de los v茅rtices tienen grado par. En un grafo semieuleriano, es posible encontrar un camino euleriano que comienza en uno de los v茅rtices de grado impar y termina en el otro v茅rtice de grado impar, pero no es posible encontrar un ciclo euleriano.

Looos caminos de la vidaa 馃幎 no son como yo pensaaaba 馃幍

Alfin encontramos el nodo G amigos

Caminos y ciclos eulerianos.: Recorre todo el grafo sin repetir una conexi贸n

Sea G un grafo conexo.
Camino euleriano:

  • Es aquel camino que recorre todo el grafo (aristas y v茅rtices) sin repetir aristas.

  • Esto se cumplir谩 si tiene exactamente dos nodos de grado impar (conexos a los caminos) adem谩s debe empezar y terminar en esos v茅rtices.

Ciclo euleriano:

  • Es aquel ciclo que recorre todo el grafo sin repetir una conexi贸n,

  • Se cumplir谩 que G tiene un ciclo euleriano si y solo si todos los v茅rtices del grafo son grado par

  • Si un grafo G admite un ciclo euleriano, entonces G es grafo euleriano.

Condici贸n para cumplir con un camino o ciclo euleriano

Creo que el concepto es Cadena Euleriana, pues esta permite repetir aunque sea los v茅rtices (nodos). En el camino no se deben repetir ni las aristas (conexiones) ni los v茅rtices (nodos).

Es cadena euleriana

Creo que te equivocaste en decir que no repite v茅rtice y es conexi贸n, eso genera confusi贸n.

  • En la teor铆a de grafos, un camino euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente una vez, empieza y termina en el mismo v茅rtice.

  • Un grafo admite un camino euleriano cuando tiene exactamente no m谩s de dos nodos de grado impar (conexos a los caminos).

  • Un grafo admite un ciclo euleriano cuando tiene todos sus nodos de grado para.

Deberia haber un video explicando la importancia de Euler para los grafos