Introducción
El emparejamiento en grafos es un tema fundamental en la teoría de grafos y tiene aplicaciones en diversas áreas como la asignación de tareas, la planificación de horarios y la optimización de recursos. En este módulo, exploraremos los conceptos básicos, algoritmos y aplicaciones del emparejamiento en grafos.
Conceptos Básicos
Definiciones Clave
- Grafo Bipartito: Un grafo \( G = (V, E) \) es bipartito si sus vértices pueden dividirse en dos conjuntos disjuntos \( U \) y \( V \) tales que cada arista conecta un vértice en \( U \) con un vértice en \( V \).
- Emparejamiento: Un emparejamiento \( M \) en un grafo es un subconjunto de aristas \( E \) tal que no comparten vértices comunes.
- Emparejamiento Máximo: Un emparejamiento es máximo si no se puede agregar más aristas sin violar la propiedad de emparejamiento.
- Emparejamiento Perfecto: Un emparejamiento es perfecto si todos los vértices del grafo están emparejados.
Ejemplo de Grafo Bipartito
Consideremos un grafo bipartito \( G \) con conjuntos de vértices \( U = {u1, u2, u3} \) y \( V = {v1, v2, v3} \):
Algoritmos de Emparejamiento
Algoritmo de Emparejamiento de Hopcroft-Karp
El algoritmo de Hopcroft-Karp es uno de los algoritmos más eficientes para encontrar un emparejamiento máximo en un grafo bipartito. Funciona en tiempo \( O(\sqrt{V}E) \).
Pasos del Algoritmo
- Inicialización: Comenzar con un emparejamiento vacío.
- Búsqueda de Camino Aumentante: Utilizar una búsqueda en anchura (BFS) para encontrar un camino aumentante.
- Aumentar el Emparejamiento: Utilizar una búsqueda en profundidad (DFS) para aumentar el emparejamiento a lo largo del camino encontrado.
- Repetir: Repetir los pasos 2 y 3 hasta que no se puedan encontrar más caminos aumentantes.
Implementación en Python
from collections import deque
def bfs(U, V, pair_U, pair_V, dist):
queue = deque()
for u in U:
if pair_U[u] == None:
dist[u] = 0
queue.append(u)
else:
dist[u] = float('inf')
dist[None] = float('inf')
while queue:
u = queue.popleft()
if dist[u] < dist[None]:
for v in U[u]:
if dist[pair_V[v]] == float('inf'):
dist[pair_V[v]] = dist[u] + 1
queue.append(pair_V[v])
return dist[None] != float('inf')
def dfs(u, U, V, pair_U, pair_V, dist):
if u != None:
for v in U[u]:
if dist[pair_V[v]] == dist[u] + 1:
if dfs(pair_V[v], U, V, pair_U, pair_V, dist):
pair_V[v] = u
pair_U[u] = v
return True
dist[u] = float('inf')
return False
return True
def hopcroft_karp(U, V):
pair_U = {u: None for u in U}
pair_V = {v: None for v in V}
dist = {}
matching = 0
while bfs(U, V, pair_U, pair_V, dist):
for u in U:
if pair_U[u] == None:
if dfs(u, U, V, pair_U, pair_V, dist):
matching += 1
return matching, pair_U, pair_V
# Ejemplo de uso
U = { 'u1': ['v1', 'v2'], 'u2': ['v2', 'v3'], 'u3': ['v3'] }
V = { 'v1': ['u1'], 'v2': ['u1', 'u2'], 'v3': ['u2', 'u3'] }
matching, pair_U, pair_V = hopcroft_karp(U, V)
print("Emparejamiento máximo:", matching)
print("Emparejamiento de U:", pair_U)
print("Emparejamiento de V:", pair_V)Ejercicio Práctico
Ejercicio 1:
Dado el siguiente grafo bipartito, encuentra el emparejamiento máximo utilizando el algoritmo de Hopcroft-Karp:
U = { 'u1': ['v1', 'v2'], 'u2': ['v2', 'v3'], 'u3': ['v3', 'v4'], 'u4': ['v1', 'v4'] }
V = { 'v1': ['u1', 'u4'], 'v2': ['u1', 'u2'], 'v3': ['u2', 'u3'], 'v4': ['u3', 'u4'] }Solución:
U = { 'u1': ['v1', 'v2'], 'u2': ['v2', 'v3'], 'u3': ['v3', 'v4'], 'u4': ['v1', 'v4'] }
V = { 'v1': ['u1', 'u4'], 'v2': ['u1', 'u2'], 'v3': ['u2', 'u3'], 'v4': ['u3', 'u4'] }
matching, pair_U, pair_V = hopcroft_karp(U, V)
print("Emparejamiento máximo:", matching)
print("Emparejamiento de U:", pair_U)
print("Emparejamiento de V:", pair_V)Resumen
En esta sección, hemos cubierto los conceptos básicos del emparejamiento en grafos, incluyendo definiciones clave y ejemplos. También hemos explorado el algoritmo de Hopcroft-Karp para encontrar emparejamientos máximos en grafos bipartitos, proporcionando una implementación en Python y un ejercicio práctico para reforzar el aprendizaje. En la siguiente sección, profundizaremos en otros algoritmos de grafos y sus aplicaciones.
Algoritmos Avanzados
Módulo 1: Introducción a los Algoritmos Avanzados
Módulo 2: Algoritmos de Optimización
- Programación Lineal
- Algoritmos de Optimización Combinatoria
- Algoritmos Genéticos
- Optimización de Colonia de Hormigas
Módulo 3: Algoritmos en Grafos
- Representación de Grafos
- Búsqueda en Grafos: BFS y DFS
- Algoritmos de Caminos Mínimos
- Algoritmos de Flujo Máximo
- Algoritmos de Emparejamiento en Grafos
Módulo 4: Algoritmos de Búsqueda y Ordenación
Módulo 5: Algoritmos de Aprendizaje Automático
- Introducción al Aprendizaje Automático
- Algoritmos de Clasificación
- Algoritmos de Regresión
- Redes Neuronales y Deep Learning
- Algoritmos de Clustering
Módulo 6: Casos de Estudio y Aplicaciones
- Optimización en la Industria
- Aplicaciones de Grafos en Redes Sociales
- Búsqueda y Ordenación en Grandes Volúmenes de Datos
- Aplicaciones de Aprendizaje Automático en la Vida Real