06 - Grafos parte 4

Question 1

¿Cuáles son las diferencias clave entre un grafo Euleriano y un grafo Hamiltoniano?

Answer 1

• Un grafo Euleriano es aquel en el que existe un recorrido (o circuito) que pasa por todas las aristas exactamente una vez. Para que un grafo sea Euleriano, todos sus vértices deben tener grado par y ser conexos.
• Un grafo Hamiltoniano es aquel que tiene un ciclo que pasa por todos los vértices exactamente una vez, sin importar cuántas veces se pasen por las aristas. No hay condiciones simples como el grado de los vértices que garanticen que un grafo sea Hamiltoniano.

Question 2

¿Qué condiciones debe cumplir un grafo para ser considerado Euleriano?

Answer 2

• Para ser Euleriano, un grafo debe cumplir dos condiciones:
  1. Debe ser conexo (es posible viajar entre cualquier par de vértices a
  través de sus aristas).
  2. Todos sus vértices deben tener un grado par, es decir, el número de aristas que inciden en cada vértice debe ser par.

Question 3

¿Cómo se aplica el Algoritmo de Fleury para encontrar un camino Euleriano?

Answer 3

• El Algoritmo de Fleury funciona de la siguiente manera:
  1. Selecciona un vértice de inicio (si se busca un circuito Euleriano, puedes empezar en cualquier vértice; si es un camino Euleriano, empieza en uno de los vértices de grado impar).
  2. En cada paso, selecciona una arista que no sea un “puente” (una arista que, al eliminarse, desconectaría el grafo), si es posible.
  3. Elimina la arista seleccionada y muévete al vértice al que está conectada.
  4. Repite este proceso hasta que no queden aristas por recorrer.

Question 4

¿Qué es un grafo Hamiltoniano y cuáles son sus aplicaciones prácticas?

Answer 4

• Un grafo Hamiltoniano es aquel que contiene un ciclo que visita todos los vértices exactamente una vez, volviendo al vértice de inicio.
• Las aplicaciones prácticas incluyen el Problema del Viajante de Comercio (TSP), la optimización de rutas en redes de transporte, la planificación de circuitos eléctricos, y en biología computacional para reconstruir secuencias de ADN.

Question 5

Explica cómo se relaciona el Problema del Cartero Chino con los grafos Eulerianos.

Answer 5

• El Problema del Cartero Chino consiste en encontrar el recorrido más corto en un grafo que pase por todas sus aristas al menos una vez, similar al trabajo de un cartero que debe recorrer todas las calles.
• Si el grafo es Euleriano, el problema se resuelve fácilmente, ya que existe un camino que pasa por cada arista una sola vez. Si no es Euleriano, es necesario añadir duplicados de algunas aristas para convertir el grafo en Euleriano.

Question 6

¿Qué diferencias existen entre un recorrido Euleriano y un tour Euleriano?

Answer 6

• Un recorrido Euleriano es una secuencia de aristas que visita cada arista del grafo exactamente una vez, pero no necesariamente regresa al vértice de inicio.
• Un tour Euleriano (o circuito Euleriano) es un recorrido cerrado que pasa por todas las aristas del grafo exactamente una vez y regresa al vértice inicial.

Question 7

¿Cómo se relacionan los grafos Eulerianos con la posibilidad de “dibujar” un grafo sin levantar el lápiz ni repetir aristas?

Answer 7

• Los grafos Eulerianos tienen la propiedad de permitir que todas sus aristas sean recorridas exactamente una vez en un ciclo cerrado.
• Esto implica que es posible dibujar el grafo en una superficie sin levantar el lápiz ni repetir aristas. Si el grafo no es Euleriano, habrá que levantar el lápiz o recorrer algunas aristas más de una vez.

Question 8

¿Cómo resuelve el Algoritmo de Hierholzer el problema de encontrar un circuito Euleriano?

Answer 8

• El Algoritmo de Hierholzer sigue estos pasos:

1. Comienza en cualquier vértice que tenga aristas sin recorrer.
2. Encuentra un ciclo recorriendo aristas no visitadas.
3. Si el ciclo contiene un vértice con aristas no visitadas, inicia un nuevo ciclo desde ese vértice y expande el ciclo original.
4. Repite hasta que todas las aristas hayan sido recorridas y se forme un único circuito Euleriano.

Question 9

¿En qué consiste el Problema del Viajante de Comercio y qué relación tiene con los grafos Hamiltonianos?

Answer 9

• El Problema del Viajante de Comercio (TSP) consiste en encontrar la ruta más corta que pase por todos los vértices de un grafo una sola vez y regrese al punto de inicio, lo que equivale a encontrar un ciclo Hamiltoniano de costo mínimo.
• La relación con los grafos Hamiltonianos es que resolver el TSP implica encontrar un ciclo Hamiltoniano en el grafo.

Question 10

¿Por qué es importante que todos los vértices tengan grado par en un grafo Euleriano?

Answer 10

• Es crucial que todos los vértices tengan grado par en un grafo Euleriano porque esto garantiza que cada vez que entres en un vértice puedas salir por otra arista sin dejar ninguna sin recorrer. Si un vértice tiene grado impar, no será posible formar un circuito que pase por todas las aristas sin dejar ninguna fuera.