Implementación de Algoritmos de Grafos: Estrategias, Caminos Mínimos y Recorridos

Creación de Grafos (Práctica 1)

Diseño de Estrategias Ganadoras

Se utiliza un dígrafo para modelar las posibles jugadas y determinar una estrategia ganadora.

• Ejemplo: Juego de Sumar 31 (donde se pueden sumar 1, 2 o 3 en cada turno).

Definición del Grafo (Ejemplo Sumar 31)

# n es el número objetivo
n = 31

# Definimos los vértices del grafo (estados del juego)
V = [1..n]

# Definimos las aristas (movimientos posibles: sumar 1, 2 o 3)
# Asumiendo que (i, j) significa que desde i se puede llegar a j
# Si se puede sumar 1, 2 o 3, las aristas serían (i, i+1), (i, i+2), (i, i+3)
E = [(i, i+k) for i in V for k in [1, 2, 3] if i+k <= n]

# Creamos el dígrafo
DJ1 = DiGraph()

# Añadimos los vértices
DJ1.add_vertices(V)

# Añadimos las aristas
DJ1.add_edges(E)

Función Kernel (Práctica 2)

La función kernel() se utiliza para encontrar el conjunto de vértices que representa una estrategia ganadora (si existe).

# Calcular el kernel del dígrafo
kernel(DJ1)

Estrategia Alternativa (Si el objetivo no es el último nodo)

Si la condición de victoria no es alcanzar exactamente el último número (ej. 31), se puede modificar el grafo eliminando dicho vértice.

# Copiamos el grafo original
DJ = copy(DJ1)

# Eliminamos el vértice objetivo (ej. 31)
DJ.delete_vertex(31)

# Calculamos el kernel del grafo modificado
kernel(DJ)

Visualización del Grafo

Se pueden definir posiciones para los vértices y visualizar el grafo.

# Generar posiciones para los vértices (ejemplo de disposición)
lista_pos = [(i, [100*(i%3), 20*(i+(i)%2)]) for i in DJ1.vertices()]
posiciones = dict(lista_pos)

# Dibujar el grafo con las posiciones especificadas
DJ1.plot(pos=posiciones)

Estrategia Ganadora en Tablero 5x5 (Objetivo 4x4)

Modelado de un juego en un tablero donde el objetivo es alcanzar la casilla (4,4).

n = 4 # Dimensión máxima x (0 a 4)
m = 4 # Dimensión máxima y (0 a 4)

DJ2 = DiGraph()

# Vértices: todas las casillas (i, j) del tablero 0..n x 0..m
V = [(i, j) for (i, j) in cartesian_product([[0..n], [0..m]])]

# Aristas: movimientos posibles (derecha, abajo, diagonal)
E1 = [((i, j), (i, j+1)) for (i, j) in V if j < m]  # Mover a la derecha
E2 = [((i, j), (i+1, j)) for (i, j) in V if i < n]  # Mover hacia abajo
E3 = [((i, j), (i+1, j+1)) for (i, j) in V if i < n and j < m] # Mover en diagonal

# Añadir vértices y aristas al grafo
DJ2.add_vertices(V)
DJ2.add_edges(E1)
DJ2.add_edges(E2)
DJ2.add_edges(E3)

# (Aquí se podría aplicar la función kernel para encontrar la estrategia)

Caminos Mínimos (Práctica 4)

Cálculo de la ruta de menor coste o distancia en un grafo ponderado.

Ejemplo: Red de Tuberías (encontrar la ruta de menor longitud o la presión mínima).

Definición del Grafo Ponderado

# Creamos un grafo ponderado (no dirigido)
Gr = Graph(weighted=True)

# Definimos las aristas con sus pesos (costes, distancias, etc.)
aristas = [
    ('A', 'B', 21), ('A', 'E', 60), ('A', 'F', 20),
    ('B', 'C', 22), ('B', 'D', 30), ('B', 'H', 19),
    ('C', 'D', 40), ('C', 'F', 41), ('C', 'H', 28),
    ('D', 'E', 28), ('D', 'H', 11),
    ('E', 'F', 21), ('E', 'H', 26),
    ('F', 'G', 25), ('F', 'H', 23),
    ('G', 'H', 25)
]

# Añadimos las aristas al grafo
Gr.add_edges(aristas)

Algoritmo de Dijkstra

Encuentra los caminos más cortos desde un nodo origen a todos los demás nodos.

# Ejecutamos Dijkstra desde el nodo 'A'
(D, T) = Gr.shortest_path_tree('A', algorithm='Dijkstra') # Usando el método específico de SageMath

# Imprimimos las distancias mínimas desde 'A'
print("Distancias: ", D)

# Visualizamos el árbol de caminos mínimos
T.plot(figsize=4, layout='tree', tree_root='A', edge_labels=True)

El árbol T muestra las conexiones necesarias para alcanzar todos los nodos desde 'A' con el mínimo coste acumulado.

Algoritmo de Kruskal (Árbol de Recubrimiento Mínimo)

Encuentra un subgrafo que conecta todos los vértices con el mínimo coste total de aristas (Árbol de Recubrimiento Mínimo - MST).

Aplicación: Determinar qué tuberías reconstruir para conectar todos los puntos con un coste mínimo total.

# Solución apartado b) - Aplicar Kruskal
(T, p) = Gr.min_spanning_tree(algorithm='Kruskal', weight_function=lambda e: e[2]) # Usando el método específico

# Imprimir el coste total del árbol de recubrimiento mínimo
print("Coste total mínimo (ej. Metros de tubería): ", p)

# Visualizar el Árbol de Recubrimiento Mínimo
T.plot(figsize=4, layout='tree', edge_labels=True)

Circuitos y Caminos Eulerianos

Un circuito euleriano recorre cada arista exactamente una vez y termina en el vértice de inicio. Un camino euleriano recorre cada arista exactamente una vez, pero puede empezar y terminar en vértices diferentes.

Definición del Grafo

# Definir un grafo mediante su diccionario de adyacencia
Gr_euler = Graph({0: [3, 4, 6, 7], 1: [3, 5, 7, 11], 2: [3, 4, 6, 8, 9, 10, 11], 3: [0, 1, 2, 7, 10], 4: [0, 2, 5, 7, 11, 12], 5: [1, 4, 6, 7, 8, 11, 12], 6: [0, 2, 5, 8, 9], 7: [0, 1, 3, 4, 5, 9, 11], 8: [2, 5, 6, 9], 9: [2, 6, 7, 8], 10: [2, 3], 11: [1, 2, 4, 5, 7], 12: [4, 5]})

Verificación y Obtención del Circuito/Camino

# Comprobar si el grafo es euleriano (todos los vértices tienen grado par)
is_eulerian = Gr_euler.is_eulerian()
print(f"¿Es Euleriano? {is_eulerian}")

# Si es euleriano, obtener el circuito
if is_eulerian:
    # Obtener el circuito como una lista de vértices
    circuit = Gr_euler.eulerian_circuit(labels=False)
    print("Circuito Euleriano (vértices):", circuit)
    # Obtener el circuito como una lista de aristas (path=True)
    # circuit_edges = Gr_euler.eulerian_circuit(path=True, labels=False)
    # print("Circuito Euleriano (aristas):", circuit_edges)

Ciclos y Caminos Hamiltonianos

Un ciclo hamiltoniano visita cada vértice exactamente una vez y regresa al vértice de inicio. Un camino hamiltoniano visita cada vértice exactamente una vez.

Verificación y Obtención del Ciclo/Camino

# Comprobar si el grafo (usaremos Gr_euler como ejemplo) es hamiltoniano
# ¡Advertencia: Este es un problema NP-completo, puede tardar mucho!
is_hamiltonian = Gr_euler.is_hamiltonian()
print(f"¿Es Hamiltoniano? {is_hamiltonian}")

# Si es hamiltoniano, obtener un ciclo hamiltoniano
if is_hamiltonian:
    # cycle = Gr_euler.hamiltonian_cycle() # Método puede variar según versión/contexto
    # print("Ciclo Hamiltoniano:", cycle)
    pass # La obtención exacta puede requerir métodos específicos

# Obtener un camino hamiltoniano (si existe)
# path = Gr_euler.hamiltonian_path() # Método puede variar
# print("Camino Hamiltoniano:", path)

Modelado de Pasatiempos: El Salto del Caballo

Encontrar un camino hamiltoniano en el grafo que representa los movimientos de un caballo en un tablero de ajedrez.

# Crear el grafo de movimientos del caballo en un tablero 5x5
G7 = graphs.KnightGraph([5, 5])

# Crear una lista de posiciones para visualizar en formato tablero
lista_pos = [(v, [100*v[1], 100*(5-1-v[0])]) for v in G7.vertices()]
posiciones = dict(lista_pos)

# Encontrar un camino hamiltoniano (el recorrido del caballo)
# ¡Advertencia: Puede ser computacionalmente intensivo!
Camino = G7.hamiltonian_path()

# Visualizar el camino encontrado sobre el tablero
if Camino:
    Camino.plot(figsize=5, pos=posiciones, vertex_labels=False, vertex_size=20)
else:
    print("No se encontró un camino Hamiltoniano (o el cálculo fue interrumpido).")