Evaluación de gráficos ponderados y completos para circuitos de Hamilton

Un circuito de Hamilton

Imagina que eres un vendedor. Quieres visitar cada casa en un vecindario determinado. Ha dibujado un mapa del vecindario en forma de gráfico usando puntos para las casas y líneas para las carreteras que conectan las casas. Desea encontrar una ruta que lo lleve a cada casa solo una vez y lo lleve de regreso al lugar donde comenzó. Este tipo de ruta se denomina circuito de Hamilton en teoría de grafos. Esta ruta visita cada vértice solo una vez y termina donde comienza. Echemos un vistazo al gráfico que ha dibujado para el vecindario:

Un circuito de Hamilton que puede tomar es el que comienza en el punto B, por ejemplo. Luego, vaya a los puntos C, D, E, A, G, F, J, I, H y luego regrese a B donde comenzó. Ha visitado cada punto o casa exactamente una vez y ha terminado donde empezó.

Un gráfico ponderado

Ahora bien, ¿qué pasaría si cada camino tuviera un costo asociado? Por ejemplo, supongamos que conduce de casa en casa. Cada camino tendrá un costo diferente ya que algunos caminos son más largos que otros y requerirán más gasolina. Más gasolina equivale a más dinero. En teoría de grafos, llamamos grafo ponderado a un gráfico en el que cada borde tiene un costo o ponderación asociado . Si agregamos el costo de los bordes, nuestro gráfico podría verse así ahora:

Ahora, debido a que tenemos un costo asociado con cada ventaja, nuestro trabajo de encontrar un circuito de Hamilton se vuelve un poco más complicado. Lo que tenemos que hacer ahora es encontrar una ruta que nos cueste menos. Oye, como vendedor, no quieres gastar más dinero del necesario. Cuanto más barato te resulte viajar, mejor. Ahora, vamos por nuestro camino, necesitamos sumar el costo asociado con cada borde, con cada camino que tomamos. El mejor circuito de Hamilton ahora es el circuito de Hamilton con el menor costo total. Mirando nuestro gráfico y mirando cuánto cuesta tomar cada camino, el mejor circuito de Hamilton es el que zigzaguea entre las casas. Por ejemplo, si comenzamos en la casa B, luego vamos a las casas H, C, I, D, J, E, F, A, G y luego volvemos a B nuevamente, nuestro costo total es 20. Ir por este camino es lo más barato. . Por supuesto, también podríamos comenzar en la casa C o en cualquier otra casa y seguir el mismo patrón en zigzag. Cualquiera de estos circuitos será el más barato y el mejor. Intente ir de otra manera y sume sus costos para ver si puede superar el costo total de 20.

Un gráfico completo

Cambiemos de tema por un momento y hablemos brevemente sobre otro tipo de gráfico que tiene relación con el número de circuitos de Hamilton. Este tipo de gráfico se llama gráfico completo . Es donde cada vértice está conectado a todos los demás vértices por una arista. Por ejemplo, el siguiente gráfico es un gráfico completo porque puede llegar a cualquier otro vértice desde cualquier vértice del gráfico. No es necesario pasar un vértice para llegar a otro.

Cuando tenemos una gráfica completa como esta, tenemos una fórmula que podemos usar para determinar el número de circuitos de Hamilton que tiene dicha gráfica. Para usar la fórmula, primero debemos contar el número de vértices que tenemos. Llamaremos N a nuestro número de vértices . Entonces, la fórmula nos dice que el número de circuitos de Hamilton que tiene una gráfica de este tipo es ( N – 1). Entonces, para nuestro gráfico, tenemos N = 5, porque tenemos 5 vértices. ¡Siguiendo la fórmula, tenemos (5 – 1)! = 4! = 4 * 3 * 2 * 1 = 24 circuitos de Hamilton presentes en este gráfico.

Ejemplo

Veamos un ejemplo. Analice este gráfico para ver si está completo y el número de circuitos de Hamilton:

Al observar este gráfico, vemos que cada vértice está conectado con todos los demás vértices. Esto hace que este gráfico sea un gráfico completo. Debido a que este es un gráfico completo, podemos calcular el número de circuitos de Hamilton. Usamos la fórmula ( N – 1) !, donde N es el número de vértices. Nuestro N = 4. ¡Entonces, tenemos (4 -1)! = 3! = 3 * 2 * 1 = 6. Tenemos un total de seis circuitos de Hamilton en este gráfico. Uno de esos circuitos es A, B, C, D, A.

Resumen de la lección

Repasemos lo que hemos aprendido ahora. Un circuito de Hamilton es una ruta que visita cada vértice una sola vez y te lleva de regreso al punto de partida. Un gráfico ponderado es un gráfico en el que cada borde tiene un costo o peso asociado. El mejor circuito de Hamilton para un gráfico ponderado es el circuito de Hamilton con el menor costo total. Un gráfico completo es un gráfico en el que cada vértice está conectado a todos los demás vértices por una arista. ¡Una gráfica completa tiene ( N – 1)! número de circuitos de Hamilton, donde N es el número de vértices en el gráfico.

Los resultados del aprendizaje

Debería tener la capacidad de hacer lo siguiente después de esta lección:

• Definir circuito de Hamilton
• Explica qué es una gráfica ponderada y cuál es el mejor circuito de Hamilton para una gráfica ponderada.
• Describir qué es una gráfica completa e identificar la fórmula para encontrar el número de circuitos de Hamilton en una gráfica completa.

Rodrigo Ricardo Editor y fundador