Modo repaso · empieza por "Qué es"

Grafos & Optimización

Concepto en palabras simples + ejemplo real, luego el ejercicio paso a paso.

Complejidad

Qué tan "difícil" es un problema

Complejidad mide cuánto tiempo (o cuántos pasos) necesita un algoritmo según crece el tamaño del problema. Un problema es NP-difícil cuando nadie ha encontrado una forma rápida de resolverlo — solo de fuerza bruta, probando muchísimas combinaciones.

En la vida real Resolver un Sudoku grande a mano puede tomarte horas. Pero si alguien te entrega un Sudoku ya resuelto, comprobar que está bien te toma segundos. Esa diferencia —difícil de resolver, fácil de comprobar— es justo la idea detrás de "NP". El Ruteo de Vehículos es NP-difícil: probar todas las rutas posibles de un repartidor con 20 direcciones tomaría más tiempo que la edad del universo.

Términos clave

P — problemas que un algoritmo resuelve rápido (ej. ordenar una lista).
NP — problemas donde, si te dan la respuesta, la puedes comprobar rápido.
NP-difícil — no se conoce forma rápida de resolverlo; solo heurísticas.

Flujo Máximo

Cuánto puede "circular" por una red

Una red de nodos conectados por arcos, donde cada arco tiene una capacidad máxima. El flujo máximo es la mayor cantidad que puede viajar del origen al destino sin exceder ninguna capacidad en el camino.

En la vida real Es como una red de tuberías de agua: cada tubo aguanta cierto número de litros por minuto. No importa qué tan grande sea el tanque de origen — el tubo más angosto en el camino limita cuánta agua llega a tu casa. Lo mismo pasa con el internet (ancho de banda de cada cable) o con el tráfico de autos (carriles de cada calle).

Términos clave

Capacidad — lo máximo que puede pasar por un arco.
Flujo — lo que realmente está pasando ahora mismo.
Corte mínimo — el "cuello de botella" que limita todo el sistema.

Planaridad

¿Se puede dibujar sin que se crucen las líneas?

Un grafo es planar cuando se puede dibujar en una hoja plana de modo que ninguna arista (línea) cruce a otra. Si por más que lo acomodes siempre queda al menos una línea cruzando a otra, el grafo no es planar.

En la vida real Es el mismo problema al diseñar un circuito impreso (PCB): las pistas de cobre no se pueden cruzar sin causar un corto circuito. Si el diseño "no es planar", los ingenieros necesitan agregar otra capa al circuito solo para resolver ese cruce. Lo mismo pasa al acomodar cables detrás de un escritorio sin que se enreden.

Términos clave

Planar — se puede dibujar sin que ninguna línea cruce otra.
Cruce — cuando dos aristas se tocan en un punto que no es un nodo real.
Subdivisión de K5 / K3,3 — un patrón "prohibido" escondido que prueba que NO es planar.

Locación en Redes

Dónde ubicar instalaciones

Dado un conjunto de clientes repartidos en una red, hay que decidir dónde ubicar p instalaciones (facilities) para que la distancia total —o la distancia máxima— hacia el facility más cercano sea lo más pequeña posible.

En la vida real Es exactamente lo que hace una cadena de farmacias o cafeterías al decidir en qué esquinas abrir sus próximas 2 sucursales, para que la gente del barrio camine lo menos posible. Las ciudades usan el mismo modelo para ubicar estaciones de bomberos o antenas de telefonía celular.

Términos clave

Facility — la instalación que se va a ubicar (tienda, hospital, antena).
p-mediana — minimizar la suma total de distancias de todos hacia su facility más cercano.
p-centro — minimizar la distancia más larga (el peor caso), no la suma.

Emparejamiento

Formar parejas óptimas, sin repetir

Un emparejamiento (matching) es un conjunto de parejas entre dos grupos, donde cada elemento aparece en como máximo una pareja. El objetivo es lograr el mayor número de parejas posible.

En la vida real Es el sistema que usan las escuelas de medicina de EE.UU. para emparejar a recién graduados con hospitales de residencia: cada persona y cada hospital tienen preferencias, y el algoritmo busca la mejor asignación sin que nadie quede repetido. Uber hace algo parecido al emparejar conductores disponibles con pasajeros cercanos.

Términos clave

Matching — conjunto de parejas donde nadie se repite.
Nodo libre — el que se quedó sin pareja en el matching actual.
Camino alternante — ruta que alterna conexiones libres/ocupadas, buscando liberar a alguien.

Ruteo de Vehículos

Planear las rutas de una flota

Dado un depósito y varios clientes con demanda, hay que diseñar las rutas de una flota de vehículos (cada uno con capacidad limitada) para atender a todos al menor costo total posible.

En la vida real Es justo lo que hace Amazon, DHL o un repartidor de comida cada mañana: decidir en qué orden visitar 20 direcciones con 3 camionetas, sin que ninguna lleve más peso del que puede cargar. También aplica a las rutas de camiones de basura o buses escolares.

Términos clave

Ruta — secuencia de paradas que hace un solo vehículo.
Demanda — cuánto necesita cada cliente (peso, cajas, etc.).
Ahorro — cuánto conviene combinar dos paradas en una sola ruta.

Par	Ahorro	¿Cabe?
1-2	7.3	Sí
2-3	5.3	No
1-3	3.2	No
1-4	1.9	No
3-4	0.1	Sí