GGH
Determine si el grafo siguiente es eureliano, de serlo, trácelo sin levantar el
lápiz del papel
El grafo representado anteriormente no
cumple con los requerimientos de un grafo
euleriano:
➢ Un 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 grafo-línea
L(G) se dice que es también
euleriano.
➢ De igual forma en punto centro no
permite que sea un grafo euleriano.
➢ Por lo tanto concluimos que no es un
grafo euleriano
Ejercicios Grafos
❖ Solución
a)
1.- C = {1, 2, 3, 4, 8, 4, 5, 6, 7}
2.- C = {1, 5, 1, 2, 3, 4, 8, 4, 7, 6}
b)
Camino = {1, 2, 3, 4, 5, 6, 7, 8}
c)
Camino = {1, 2, 3, 4, 8, 7, 6, 5, 1}
d)
Encuentra un ciclo hamiltoniano para cada grafo
a)
Ciclo hamiltoniano: {a, e, f, j, d, c, i, k, g, h, b, a}
b)
Ciclo hamiltoniano: {a, c, h, f, i, j, g, e, b, d, a}
c)
Ciclo hamiltoniano: {a, h, j, d, c, g, f, e, b, a}
Solución
A)
SOLUCION:
a) No es posible encontrar la solución para un ciclo hamiltoniano.
b) En el ejercicio 1, no retirando, eliminando un vértice logramos tener
un ciclo hamiltoniano.
En el ejercicio 2 eliminaría el punto o vértice c, logro un ciclo
hamiltoniano, se puede eliminar algún otro, dependiendo del vértice
de inicio
• Dado un grafo con un ciclo de Hamilton, si suprimimos una de sus aristas se obtiene un camino de Hamilton.
• Un grafo puede tener un camino de Hamilton y no poseer ningún ciclo de Hamilton.
• Un grafo con vértice de grado uno no posee ningún ciclo de Hamilton, puesto que en estos ciclos cada vértice del grafo es incidente con dos aristas.
• Si un vértice de un grafo tiene grado dos, entonces las dos aristas incidentes en este vértice forman parte de cualquier ciclo de Hamilton que hubiera
en el grafo.
• Cuando se está construyendo un ciclo de Hamilton y ́este pasa por un vértice, entonces ignoramos a efecto de su construcción, las restantes aristas
incidentes en este vértice que no forman parte del ciclo.
• Un ciclo de Hamilton no puede contener otro ciclo más pequeño dentro de él.
• Un grafo de Hamilton no puede tener vértices de corte o articulación.
• Si G tiene un ciclo de Hamilton, entonces todos los vértices tienen grado mayor o igual que 2.
• A pesar de la aparente analogía entre grafos eulerianos y hamiltonianos, hay profundas diferencias en su estudio. La fundamental es que no se
conoce ninguna caracterización para los grafos hamiltonianos.
Solución:
Analizando el grafo presentado anteriormente llegamos a la conclusión que no es posible obtener un camino o ciclo
Hamiltoniano ya que no cumple, con la primordial característica de pasar por todos los vértices solo una vez logrando
Llegar al punto o vértice de inicio. No importa el punto de inicio, no logramos obtener un ciclo o camino hamiltoniano.
a) Encuentra un circuito euleriano para el grafo de la
figura adjunta.
b) Si se elimina la arista {d, e} encuentra un
recorridoeuleriano para el subgrafo resultante.
Solución:
A)
Solución
Circuito euleriano
{a – d – h – i - f – j – k – g – c – b – f - e – d – b – a}
b)
solución:
{a – b – c – g – k – j – i – h -a}
1.- Diseña un grafo conexo que:
a) No tenga circuitos eulerianos ni ciclos hamiltonianos.
b) Tenga un circuito euleriano pero no tenga ciclos hamiltonianos.
c) Tenga un ciclo hamiltoniano, pero no tenga un circuito euleriano.
d) Tenga un ciclo hamiltoniano y un circuito euleriano.
2.- Investiga que características debe tener un grafo para que
un circuito euleriano sea también un ciclo hamiltoniano.
Sea G un grafo sin vértices aislados. Un circuito que contiene todas las aristas
de G recibe el nombre de circuito euleriano. Un circuito euleriano y un ciclo
hamiltoniano es una trayectoria que empieza y termina en el mismo vértice y
recorre cada arista exactamente una vez.
Identifique la ruta que conecta el punto a con el punto z tocando todos los
vértices del grafo
Imaginemos ahora cinco países, pi, que poseen entre ellos las siete
fronteras que se representan en la Figura 7 (a) y que hemos indicado con
fi. ¿Será posible iniciar una ruta partiendo de uno de los países, atravesar
cada una de las fronteras una sola vez, y regresar al
país de partida?
SOLCUCIÓN:
Las fronteras de estos países se encuentran
en puntos un poco complejos, complicando
una trayectoria segura de llegar al mismo
punto, o en caso de que repitan pasar por
alguna frontera más de una vez.
