Notas Programación 3

Éstas notas fueron traducidas del libro Algorithm Design by Jon Kleinberg.

Marcela Pintos | Cursada en FING 2022

Capítulo 1 - Algunos Problemas Represantativos
Se considera un conjunto M = {m1,...,mn} de n hombres, y un conjunto W = {w1,...,wn} de n mujeres. M x W
denota el conjunto de todos los posibles pares ordenados de la forma (m,w), donde m ∈ M y w ∈ W.

Emparejamiento: Es un conjunto S de pares ordenados, donde cada par partenece a M x W, con la

propiedad de que cada elemento de M y cada elemento de W aparece a lo sumo en un par de S.

Emparejamiento Perfecto: Es un emparejamiento S´, con la propiedad de que cada elemento de M y

cada elemento de W aparece exactamente en un par.

Inestabilidad: Un par (m,w´) es una inestabilidad con respecto a un emparejamiento perfecto S, si (m,w´)
no pertenece a S pero tanto m como w´ se prefieren el uno al otro antes que a su pareja en S.

Emparejamiento Estable: Decimos que un emparejamiento S es estable si (1) es perfecto y (2) no hay
ninguna inestabilidad con respecto a S.

➤ Existe por lo menos un emparejamiento estable por cada lista de preferencias entre los hombres y las
mujeres.

Algoritmo Gale - Shapley

Inicialmente todo m ∈ M y toda w ∈ W estan solteros
While haya un hombre m que no esté comprometido y no se haya propuesto a todas las mujeres
Elegir a ese hombre m
Sea w la mujer mejor calificada en la lista de preferencias de m a la cual m aún no se ha propuesto
If w no está comprometida
(m,w) se comprometen
Else // w está comrometida con m´
If w prefiere a m´ antes que a m
m sigue estando libre
Else // w prefiere a m antes que a m´
(m,w) se comprometen
m´ pasa a estar soltero
Endif
Endif
Endwhile
Return el conjunto S de parejas comprometidas
Propiedades de G-S
(1.1) w permanece comprometida desde el momento en que w recibe su primer propuesta
de matrimonio, y la secuencia de parejas en la que ella está comprometida va mejorando
(en términos de su lista de preferencias).

(1.2) La secuencia de mujeres a las que m se propone va empeorando (en términos de su

lista de preferencias).

(1.3) El algoritmo Gale - Shapley termina luego de a lo sumo n2 iteraciones del while.

(1.4) Si un hombre m está soltero en algún punto de la ejecución del algoritmo, entonces
existe una mujer w a la cual no se ha propuesto todavía.

(1.5) El conjunto S retornado cuando termina una ejecución del algoritmo es un

emparejamiento perfecto, más aún, (1.6) S es un emparejamiento estable.

➤ Todas las ejecuciones producen el mismo emparejamiento estable.

Pareja Válida: Una mujer w es una pareja válida de un hombre m si existe un emparejamiento estable que
contiene el par (m,w). (Un hombre m es una pareja válida de una mujer w si existe un emparejamiento
estable que contiene el par (m,w)).
Mejor Pareja Válida: Una mujer w es la mejor pareja válida de un hombre m si w es pareja válida de m, y
además no existe ninguna mujer que sea pareja válida de m y que la califique mejor que a w.
Notación: best(m) es la mejor pareja válida de m.

(1.7) Cada ejecución de G-S termina en el set S*, donde S* = { (m,best(m)) / m ∈ M}.

➤ El orden de las propuestas de matrimonio en G-S no tienen ningún efecto en el retorno.

Peor Pareja Válida: Un hombre m es la peor pareja válida de una mujer w si m es una pareja válida de w,
y además no existe ningún hombre que sea pareja válida de w y que lo califique peor que a m.
Notación: worst(w) es la peor pareja válida de w.

(1.8) Cada ejecución de G-S termina en el set S*, donde S* = { (worst(w),w) / w ∈ W}.

➤ Para cualquier entrada, el lado que hace la propuesta en G-S termina con el mejor emparejamiento
estable posible (desde su perspectiva), mientras que el lado que no hace la propuesta termina con el peor
emparejamiento estable posible.

5 Problemas Representativos

Intervalo de Planificación (Interval Scheduling)

Hay n solicitudes etiquetadas 1,...,n donde cada solicitud i especifica un tiempo de comienzo si y un
tiempo de finalización fi. Naturalmente se tiene que si < fi para todo i.
2 solicitudes i y j son compatibles si los intervalos de las solicitudes no se superponen, es decir sucede
uno de los siguientes casos: 1. fi ≤ sj
2. fj ≤ si
Un subconjunto A de solicitudes es compatible si todos los pares de solicitudes i,j ∈ A, i ≠ j son
compatibles.

El objetivo es seleccionar un subconjunto compatible de solicitudes del mayor tamaño posible.

Intervalo de Planificación Con Valor (Weighted Interval Scheduling)

Se tiene el problema de Intervalo de Planificación, pero ahora cada solicitud i tiene un valor v asociado,
con vi > 0.

El objetivo es seleccionar un subconjunto compatible de solicitudes que tenga el mayor valor total
posible.

➤ Por ejemplo consiedere que si v1 es mayor a la suma de todos los valores restantes vi, entonces la
soluión óptima debe inlcuir la solicitud 1, sin importar la configuración del conjunto completo de intervalos.

Emparejamiento Bipartito (Bipartite Matching)

Grafo Bipartito: Un grafo G = (V,E) es bipartiro si su conjunto de nodos V puede ser dividido entre 2
conjuntos X e Y, donde cada arista tiene un nodo en X y otro nodo en Y.
Un emparejamiento en un grafo G = (V,E) es un conjunto de aristas M ⊆ E, con la propiedad de que
cada nodo aparece a lo sumo en una arista de M.
Un emparejamiento perfecto en un grafo G = (V,E) es un conjunto de aristas M ⊆ E, con la propiedad
de que cada nodo aparece exactamente en una arista de M.

Considere un grafo bipartito G´ con un conjunto X de n hombres, un conjunto Y de n mujeres, y

una arista desde cada nodo en X a cada nodo en Y. Entonces los emparejamientos y
emparejamientos perfectos en G´ son precisamente los emparejamientos y emparejamientos
perfectos entre el conjunto de hombres y mujeres.

Problema del Emparejamiento Perfecto: Dado un grafo G bipartito aleatorio, encontrar un emparejamiento
de tamaño máximo. Si |X| = |Y| = n, entonces existe un emparejamiento perfecto si y solo si el
emparejamiento máximo tiene tamaño n.

Conjunto Independiente (Independent Set)

Dado un grafo G =(V,E), decimos que un conjunto S ⊆ V de nodos es independiente si 2 nodos en S
no están conectados por una arista.

Problema del Conjunto Independiente: Dado un grafo G, hayar un conjunto de nodos independiente de
mayor tamaño posible. Éste problema describe cualquier situación en la que se trata de elegir entre una
colección de objetos donde hay pares de conflictos entre algunos de los objetos.
➤ Solución de Intervalo de Planificación con Conjunto Independiente: Se define un grafo G = (V,E) donde
cada nodo son los intervalos, y existe una arista entre cada par de nodos si estos se superponen; el
conjunto independiente de nodos en G son los subconjuntos compatibles de intervalos.

Competencia de Localidades (Competitive Facility Location)

Considere 2 empresas que tienen franquicias de cafés a lo largo de un país, y actualmente están
compitiendo por compartir el mercado en un área geográfica. Suponga que ellos deben lidiar con
regulaciones de la zona, donde no pueden haber 2 franquicias localizadas muy juntas, y cada uno está
tratando de hacer que sus localidades sean lo más convenientes posibles.

El área geográfica en cuestión es dividida entre n zonas, enumeradas entre 1,...,n. Cada zona i tiene un
valor bi, que es el ingreso obtenido por cualquiera de las empresas si abre una franquicia ahí. Finalmente,
ciertos pares de zonas (i,j) son adyacentes, y las regulaciones de la zona prohíben que hayan
franquicias en 2 zonas adyacentes (sin importar de qué empresa son las franquicias), tambien se prohíbe
que 2 franquicias se abran en la misma zona.

Se modela el problema como el siguiente: Sea un grafo G = (V,E), donde V es el conjunto de zonas, y (i,j)
es una arista en E si las zonas i y j son adyacentes.
El conjunto de las franquicias abiertas forma un conjunto independiente de nodos en G.

Capítulo 2 - Básicos sobre Análisis de Algoritmos

1° definición de eficiencia:
Un algoritmo es eficiente si cuando es implementado es ejecutado rápidamente en instancias reales de
entradas.

2° definición de eficiencia:
Un algoritmo es eficiente si logra un mejor peor-caso en un nivel analítico, comparado con la búsqueda a
la fuerza bruta.

3° definición de eficiencia:
Un algoritmo es eficiente si es ejecutado en un orden polinómico.

Tiempo Polinómico como definición de eficiencia

Suponga que un algoritmo tiene la siguiente propiedad: Existen constantes c > 0 y d > 0 que para cada
entrada de tamaño N, su tiempo de ejecución está acotado por cNd pasos computacionales primitivos. Si
éste tiempo de ejecución se mantiene para algún c y d, entonces decimos que el algoritmo tiene un tiempo
de ejecución polinómico.
 Orden Asintótico de Crecimiento

Para proveer una cota sobre el tiempo de ejecución de un algoritmo, generalmente contamos el número
de los pasos del pseudocódigo que es ejecutado; en este contexto, un paso consiste en asignar un valor
a una variable, ver el valor de la entrada de un array, seguir un puntero, o hacer una operación aritmética
en un número.

O - Límites Superiores Asintóticos

Sea T(n) una función tal que es el peor-caso de ejecución de un algoritmo de entrada de tamaño n.
(Asumiremos que todas las funciones toman valores no negativos.)

Dada otra función f(n), diremos que T(n) es O(f(n)), es decir T(n) es de orden f(n), si para cierto n
suficientemente grande, T(n) está acotado superiormente por un múltiplo constante de f(n).

➤ T(n) es O(f(n)) si existen constantes c > 0 y n0 ≥ 0 tal que para todo n ≥ n0, tenemos T(n) ≤ cf(n).

Ω - Límites inferiores Asintóticos

Diremos que T(n) es Ω(f(n)), si para cierto n suficientemente grande, T(n) está acotado inferiormente por
un múltiplo constante de f(n).

➤ T(n) es Ω(f(n)) si existen constantes ϵ > 0 y n0 ≥ 0 tal que para todo n ≥ n0, tenemos T(n) ≥ ϵf(n).

Θ - Límites Asintóticos Estrechos

➤ Diremos que una función es Θ(f(n)) si es O(f(n)) y tambien Ω(f(n)).

Propiedades de las tasas de Crecimiento

𝑓(𝑛)
(2.1) Sean f y g dos funciones tales que lim 𝑔(𝑛)
existe y es igual a un número c > 0, entonces diremos
𝑛→∞
que f(n) = Θ(g(n)).

(2.2) a) Si f = O(g) y g = O(h), entonces f = O(h)

b) Si f = Ω(g) y g = Ω(h), entonces f = Ω(h)

(2.3) Si f = Θ(g) y g = Θ(h), entonces f = Θ(h)

(2.4) Suponga que f y g son dos funciones tales que dada otra función h, tenemos que f = O(h) y g = O(h).
Entonces f + g = O(h)
(2.5) (Generalización de 2.4) Sea k una constante fija, y sea f1, …, fk y h funciones tales que fi = O(h) para
todo i. Entonces f1 + … +fk = O(h)

(2.6) Suponga que f y g son dos funciones tales que g = O(f). Entonces f + g = Θ(f)
➤ Si se tiene una suma de funciones, entonces la que crece más rápido de todas es un límite asintótico
estrecho de la suma.

Límites Asintóticos para algunas Funciones Comunes

● Polinómicos: Recuerde que un polinomio es una función f(n) = a0 + a1n + a2n2 + … + adnd para algun
entero d > 0, donde el coeficiente final ad es distinto de 0. Su orden de crecimiento es determinado por
su término de mayor orden (ad). Es de nuestro interes que las funciones tomen valores no negativos, por
lo que restrictiremos ad > 0.

(2.7) Sea f un polinomio de grado d, donde el coeficiente ad es positivo. Entonces f = O(nd)

➤ Tambien se puede mostrar que f = Ω(nd), por lo que tendremos que f = Θ(nd).

● Logarítmicos: (logb n = x ⇔ bx = n) Una forma de tener un sentido aproximado de qué tan rápido crece
logb n es notando que, si redondeamos hacia abajo al entero más cercano, es un número menos que la
cantidad de dígitos que tiene el número n en su representación en la base b. (Por ejemplo, 1 + log2 n
redondeado hacia abajo, es el número de bits necesarios para representar n).

(2.8) Para cada b > 1 y cada x > 0, tenemos que logb n = O(nx)

➤ loga n = logb n ÷ logb a, por lo que loga n = Θ(logb n)

● Exponenciales: Son de la forma f(n) = rn para alguna constante r. Consideraremos r > 1, por lo que
resulta una función que crece muy rápido.

(2.9) Para cada r > 1 y cada d > 0, tenemos nd = O(rn)

Implementando el Algoritmo Gale - Shapley usando Arreglos y Listas

Preferencias de Hombres: Se tiene un arreglo donde en las celdas están los hombres, y cada hombre
tiene asociado un arreglo donde se encuentran las mujeres ordenadas según las preferencias de cada
hombre.

Preferencias de Mujeres: Análogo al de los hombres.

Hombres Libres: Se utiliza una pila de hombres.

Next: Es un arreglo donde los índices son los hombres, y en cada celda se encuentra la posición de la
próxima mujer en su lista de preferencias.
 Current: Es un arreglo donde los índices son las mujeres, y en cada celda se encuentra el identificador
del hombre al cuál están comprometidos. Se utiliza un valor auxiliar para cuando la mujer no está
comprometida aún.

Ranking: Es una matriz de nxn donde en la celda ij se encuentra la posición de mj en la lista de

preferencias de wi.

➤ Esto va a permitir que todas las operaciones dentro del while sean de O(1).

Una recorrida sobre los tiempos más comunes de ejecución

● Tiempo Linear: Un algoritmo que es ejecutado en O(n) se dice que tiene un tiempo lineal. Una muy
natural propiedad es que su tiempo de ejecución es como mucho una constante por el tamaño de la
entrada.

● O(nlogn): Es el tiempo de ejecución de cualquier algoritmo que divide la entrada entre 2 pedazos
iguales, resuelve cada pedazo recursivamente y luego combina las dos soluciones en tiempo linear.

● Tiempo cuadrático: O(n2) ilustra el tiempo de un algoritmo que hace una búsqueda entre todos los pares
posibles de una entrada (la cantidad son combinaciones de n tomadas de da 2), pasando un tiempo
constante en cada par. También ilustra un par de loops anidados donde cada loop tiene un tiempo O(n).
● Tiempo Cúbico: Algoritmos con loops anidados más elaborados nos llevan a un O(n3).

● O(nk): Obtenemos un tiempo de éste estilo para cualquier constante k cuando buscamos entre todos los
subconjuntos de tamaño k.

● Más allá de tiempo polinómico: 2 tipos que aparecen frecuentemente son 2n y n!.

● Tiempo sublinear: Hay casos en los cuales uno encuentra tiempos de ejecución asintóticamente
menores que los tiempos lineares. Como solamente para leer la entrada toma tiempo linear, estas
situaciones suelen surgir en un modelo de computación donde la entrada puede ser consultada
indirectamente en vez de leerla completamente, y el objetivo es minimizar la cantidad de consultas que
se deben hacer. Un ejemplo es el algoritmo de la búsqueda binaria.

Capítulo 3 - Grafos

Definiciones

Grafo: Consiste en un conjunto V de nodos y un conjunto E de aristas, donde cada arista une dos nodos.
Una arista e ∈ E es un subconjunto de dos elementos de V: e = {u,v}, para algunos u,v ∈ V.

Grafo Dirigido: Consiste en un conjunto V de nodos y un conjunto E’ de aristas dirigidas. Cada e’ ∈ E’ es

un par ordenado (u,v) para algunos u,v ∈ V.
Camino: Un camino en un grafo G = (V,E) es una secuencia P de v1, …, vk-1, vk con la propiedad de que
cada par consecutivo vi, vi+1 está unido por una arista en G.

Camino simple: Es un camino tal que todos los vértices son distintos entre sí.

Ciclo: Es un camino v1, …, vk-1, vk con k > 2, donde los primeros k-1 nodos son todos distintos entre sí, y
además v1 = vk.

➤ Las definiciones anteriores se pueden extender naturalmente a grafos dirigidos, agregando que la
secuencia de nodos debe respetar las direcciones de las aristas.

Grafo Conexo: Decimos que un grafo no-dirigido es conexo si para todo par de nodos u y v, existe un
camino de u hacia v.

Grafo Fuertemente Conexo: Decimos que un grafo dirigido es fuertemente conexo si para todo par de
nodos u y v, existe un camino de u hacia v y un camino de v hacia u.

Distancia: Definimos la distancia entre dos nodos u y v como la mínima cantidad de aristas en un camino
u-v.

Árbol: Decimos que un grafo no-dirigido es un árbol si es conexo y no tiene ciclos.

(3.1) Todo árbol de n nodos tiene n-1 aristas.

(3.2) Sea G un grafo no-dirigido. Las dos primeras afirmaciones implican la tercera.
1. G es conexo
2. G no tiene ciclos
3. G tiene n-1 aristas

Breadth-First Search (BFS - Búsqueda en Amplitud)

Tal vez sea el algoritmo más simple para determinar la conectividad entre los nodos s y t. Se explora hacia
afuera desde el nodo s en todas las direcciones posibles, añadiendo nodos una ‘’capa’’ a la vez.
Se empieza desde el nodo s e incluimos todos los nodos que están unidos a s por una arista (ésta sería la
primer capa de la búsqueda). Luego, inlcuimos todos los nodos adicionales que están unidos por una arista
a cualquier nodo de la primera capa, y se continúa hasta que no se encuentran más nodos.

●La capa L1 consiste en todos los nodos que tienen una arista en común con s. A veces se denotara L0
como la capa que contiene al nodo s.
●Asumiendo que ya definimos las capas L1, …, Lj entonces la capa Lj+1 consiste en todos los nodos que no
pertenecen a ninguna capa anterior y que tiene una arista con un nodo en la capa Lj.

(3.3) Para cada j ≥ 1, la capa Lj producida por BFS consiste en todos los nodos que están a una distancia j
de s. Hay un camino de s a t si y solo sí t aparece en alguna capa.

➤ Otra propiedad de BFS es que éste produce un árbol cuya raíz es s, y todos los demás nodos son los
nodos que se pueden alcanzar por un camino desde s.
➤ Nos referiremos al resultado de BFS como un conjunto R de nodos, tal que es la componente conexa de
G conteniendo a s

(3.4) Sea T el árbol producido por BFS, además sean x e y nodos en T pertenecientes a las capas Li y Lj
respectivamente, y sea (x,y) una arista en G. Entonces i y j difieren en a lo sumo 1.

(3.5) El sigiuente algoritmo producirá el conjunto R, que será la componente conexa de G conteniendo a s.

Sea R el conjunto de nodos el cuál consistirá en todos los nodos en los que s tiene un camino
Inicialmente R = {s}
While hay una arista (u,v) donde u ∈ R y v ∉ R
Agregar v a R
EndWhile

Algoritmo BFS
La lista de adyacencia es ideal para BFS, además usaremos un arreglo Descubierto de largo n, y
setearemos Descubierto[v] = true en cuanto BFS descubra a v. Para mantener a los nodos en alguna capa
Li, tendremos una lista L[i] para cada i = 0,1,2,...

BFS(s):
Establecemos Descubierto[s] = true y Descubierto[v] = false para los demás nodos
Inicializamos L[0] que consiste en un único elemento s
Establecemos el contador de capas i = 0
Inicializamos el árbol de BFS T como vacío
While L[i] no sea vacía
Inicializar una lista vacía L[i+1]
For cada nodo u ∈ L[i]
Considerar cada arista (u,v) incidente a u
If Descubierto[v] = false
Seteamos Descubierto[v] = true
Añadimos la arista (u,v) al árbol T
Añadimos v a la lista L[i+1]
Endif
EndFor
Incrementamos el contador de de capas i en uno
EndWhile

(3.11) La anterior implementación de BFS corre en O(m + n) si la representación del grafo es dada por una
lista de adyacencia.
 Depth-First Search (DFS - Búsqueda en Profundidad)
Otro método natural para encontrar los nodos que pueden ser alcanzados por s es DFS. Se empieza
desde el nodo s y se sigue la primer arista hasta encontrar el nodo v que se conecta con s, luego se sigue
la primer arista que empieza en v hasta llegar a otro nodo m, y así sucesivamente hasta no encontrar
ningún otro nodo. Luego, se retrocede hasta encontrar un nodo al que no le hayamos explorado todos sus
vecinos, y empezar desde ahí. Nos da una noción de recursividad.

➤ Al igual que BFS, produce un árbol (diferentes entre sí) cuya raíz es s y éste es la componente conexa
de G conteniendo a s.

Sea R el conjunto de nodos el cuál consistirá en todos los nodos en los que s tiene un camino
Marcar u como ‘’Explorado’’ y añadir u a R
For cada arista (u,v) incidente a u
If v no está marcado como explorado entonces
Invocar recursivamente a DFS(v)
Endif
Endfor

(3.6) Dada una llamada recursiva de DFS(u), todos los nodos que están marcados como explorados entre
la invocación y la finalización de la llamada recursiva son descendientes de u en el árbol T que produce.

(3.7) Sea T el árbol de DFS, sean x e y nodos en T, y sea (x,y) una arista en G que no es una arista en T.
Entonces uno de x o y es ancestro del otro en T.

Algoritmo DFS
Usaremos un arreglo Descubierto de largo n, y setearemos Descubierto[v] = true cuando termine de
explorar a los vecinos de v.

➤ Si queremos que algoritmo tambien encuentre el árbol de DFS, para cada nodo u en la pila tenemos
que mantener registrado el nodo que causó que u se añadiera a la pila. Pondré en negrita lo que se
necesita para generar el árbol. Tendremos un arreglo Padre de largo n y cada vez que un nodo u haga que
otro nodo w se añada a la pila, actualizaremos Padre[w] = u (el nodo s no tendrá padre).

DFS(s):
Inicializar S como una pila con el nodo s
While S no sea vacía
Desapilar u de S
If Descubierto [u] = false
Setear Descubierto [u] = true
For cada arista (u,v) incidente a u
Añadir v a la pila S
 Padre[v] = u
Endfor
Endif
EndWhile

(3.12) El anterior algoritmo implementa DFS, en el sentido que visita los nodos exactamente en el mismo
orden que el procedimiento recursivo de DFS.

(3.13) La anterior implementación de DFS corre en O(m + n) si la representación del grafo es dada por una
lista de adyacencia.

El Conjunto de todas las Componentes Conexas

(3.8) Para dos nodos cualquiera s y t en un grafo, sus componentes conexas son iguales o disjuntas.

Empezamos con un nodo cualquiersa s, y utilizamos BFS o DFS para generar su componente conexa.
Luego, si encontramos algun otro nodo v que no se incluyó en la búsqueda de s, entonces realizamos
nuevamente BFS o DFS para generar su componente conexa (que será disjunta a la de s). Continuamos
hasta que todos los nodos hayan sido visitados.

Representando Grafos
Sea un grafo G = (V,E) donde |V| = n y |E| = m, los tiempos de ejecución estarán determinados por estos
dos parámetros.

Matriz de Adyacencia
Es una matriz A de nxn donde A[u,v] es 1 si el grafo contiene una arista (u,v), es 0 en caso contrario. Si el
grafo es no-dirigido, entonces la matriz es simétrica ya que A[u,v] = A[v,u] para todo u,v ∈ V.

➤ Permite fijarnos en O(1) si una arista (u,v) pertenece al grafo.

(3.10) La representación toma un espacio de Θ(n2), por lo que para un grafo con pocas aristas no es lo
adecuado. Además, para fijarnos la cantidad de aristas adyacentes a un nodo nos va a costar Θ(n).

Lista de Adyacencia
Es un arreglo Adj, donde Adj[v] contiene una lista con todos los nodos adyacentes a v. Si el grafo es
no-dirigido, entonces una arista (v,w) ∈ E aparece en dos listas: el nodo w aparece en la lista para el nodo
v, y el nodo v aparece en la lista para el nodo w.

(3.10) La representación toma un espacio de O(m + n).

➤ El largo de una lista Adj[v] es nv, por lo que permite fijarnos en O(nv) si una arista (u,v) pertenece al
grafo.
Grado de un nodo: Se define el grado nv de un nodo como el número de aristas incidentes que éste tiene.

(3.9) ∑ nv = 2m. (La suma de los grados de todos los nodos de un grafo es el doble de la cantidad de
𝑣∈𝑉
aristas que tiene el grafo).

Probando el Bipartinismo: Una aplicación de BFS

Podemos decir que un grafo es bipartito si es posible colorear sus nodos de rojo y azul, donde cada arista
tiene un nodo de color rojo y el otro nodo de color azul.

Para hacer esto con BFS, colorearemos el nodo inicial s de rojo, luego todos los nodos de la capa L1 de
azul, todos los nodos de la capa L2 de rojo; por lo que tendremos que los nodos pertenecientes a una capa
impar serán pintados de azul y los nodos de una capa par serán pintados de rojo.

(3.14) Si un grafo G es bipartito, entonces no puede contener un ciclo impar.

(3.15) Sea G un grafo conexo, y sean L1, L2, … las capas producidas por BFS empezando por el nodo s.
Entonces exactamente una de las dos siguientes declaraciones debe ocurrir:
1. No hay ninguna arista de G uniendo dos nodos de la misma capa. En este caso, G es un
grafo bipartito donde los nodos que pertenecen a capas par pueden ser coloreados en rojo,
y los nodos que pertenecen a capas impares pueden ser coloreados azul.
2. Hay una arista de G uniendo dos nodos de una misma capa. En este caso, G contiene un
ciclo de longitud impar, por lo que no puede ser bipartito.

Grafos Dirigidos

Lista de Adyacencia
Para representarlos se usa una versión de la lista de adyacencia.
En vez de que cada nodo tiene una única lista con todos sus vecinos, cada nodo va a tener dos listas
asociadas: una lista consiste en los nodos que tiene la arista saliente, y la otra lista consiste en los nodos
que tiene la arista entrante.

Conectividad Fuerte
Alcanzable mutuamente: Decimos que dos nodos u y v son alcanzables mutuamente en un grafo dirigido
si hay un camino de u a v y tambien hay un camino de v a u.

➤ Un grafo dirigido es fuertemente conexo si cada par de nodos es alcanzable mutuamente.

(3.16) Si u y v son alcanzables mutuamente, y v y w son alcanzables mutuamente, entonces u y w son

alcanzables mutuamente.
Existe un simple algoritmo de orden linear (O(m + n)) para verificar si un grafo dirigido es fuertemente
conexo (se basa en 3.16): Tomamos cualquier nodo s y ejecutamos BFS en G empezando en s, luego
corremos BFS empezando en s en Grev (Grev es G pero invirtiendo las direcciones de las aristas). Ahora, si
una de estas dos búsquedas no alcanza todos los nodos, entonces G no es fuertemente conexo.

Componente Fuerte: La componente fuerte conteniendo un nodo s en un grafo directo es el conjunto de

todos los nodos v los cuales s y v son alcanzables mutuamente.

(3.17) Dados dos nodos s y t cualesquiera en un grafo dirigido, sus componentes fuertes son iguales o
disjuntas.

Orden Topológico

DAG (Grafo Dirigido Acíclico): Si un grafo dirigido no contiene ciclos, entonces lo nombramos como un
DAG.

Los DAGs pueden ser utilizados para decodificar relaciones de precedencia o dependencias de una forma
natural. Suponga que tenemos un conjunto de tareas etiquetadas {1, …, n} que necesitan ser ejecutadas, y
además existen ciertas dependencias entre algunos pares (i,j) de tareas (i debe ejecutarse antes que j).

Éste problema se puede representar como un grafo dirigido, donde las tareas son los nodos, y una arista
dirigida (i,j) aparece en el grafo siempre que i deba realizarse antes que j. Para que la relación de
precedencia tenga sentido, el grafo resultante G debe ser un DAG (si éste contiene un ciclo, entonces no
existe ninguna manera de realizar las tareas de éste ciclo).

Orden Topológico: Para un grafo dirigido G, decimos que un orden topológico en G es un ordenamiento
de sus nodos v1, …, vn, donde en cada arista (vi,vj) se tiene que i < j. En otras palabras, todas las aristas
apuntan ‘’hacia afuera’’ según el ordenamiento.

(3.18) Si G tiene un orden topológico, entonces es un DAG.

(3.19) En cada DAG, existe un nodo v sin aristas entrantes.

(3.20) Si G es un DAG, entonces G tiene un orden topológico.

Para computar un orden topológico en G:

Encontrar un nodo v sin aristas entrastes y colocarlo primero en el orden
Borrar v de G
Recursivamente computar un orden topológico de G-{v} (y colocar este orden luego de v)

➤ Éste algoritmo corre en O(n2).

➤ Se puede lograr O(m + n) si somos mas eficientes hayando los nodos, lo cual haremos de la siguiente
forma iterativa:
Declaramos un nodo como activo si todavía no se ha eliminado del algoritmo, y mantenemos las dos
siguientes cosas:
1. Para cada nodo w, el número de aristas entrantes que tiene de nodos activos, y
2. El conjunto S de todos los nodos activos en G que no tienen aristas entrantes de otros nodos activos.

Al principio todos los nodos están activos, por lo que podemos inicializar (1) y (2) en una sola pasada de
los nodos y aristas. Luego, cada iteración consiste en seleccionar un nodo v del conjunto S y borrarlo.
Después de borrar v, recorremos todos los nodos w que tienen una arista con v, y bajamos en uno el
número de aristas entrantes activas que estamos manteniendo para w. Si esto causa que el número de
aristas entrantes activas baje a cero, entonces añadimos w al conjunto S.

Capítulo 4 - Algoritmos Codiciosos

Un algoritmo es codicioso si construye una solución en pocos pasos, tomando una decisión en cada paso
para optimizar la solución según algún criterio.

Intervalo de Planificación
Tenemos un conjunto de solicitudes {1, …, n}, donde la i-ésima solicitud corresponde a un intervalo de
tiempo que comienza en s(i) y termina en f(i).

Conjunto compatible: Un subconjunto de solicitudes en compatible si ninguna de las solicitudes se

solapan en el tiempo.

Conjunto óptimo: Un subconjunto compatible es óptimo si éste tiene el mayor tamaño posible.

Algoritmo

Primero ordenamos las n solicitudes según su tiempo de finalización, por lo que tendremos que f(i) ≤ f(j)
cuando i < j (ésto se hace en O(nlogn)). Luego construimos un arreglo S[1…n] en O(n) con la propiedad de
que S[i] contiene el valor s(i).

Sea R el conjunto de todas las solicitudes, y A un conjunto vacío

While R no sea vacío
Elegir una solicitud i ∈ R que tiene el menor f(i) posible
Añadir la solicitud i a A
Borrar todas las solicitudes de R que no son compatibles con la solicitud i
Endwhile
Return el conjunto A como el conjunto de las solicitudes aceptadas

(4.1) El conjunto A retornado por el algoritmo es un conjunto compatible de solicitudes.

(4.2) Sea k = |A|, y sea O un conjunto óptimo de intervalos. Para todos los intervalos r ≤ k, tenemos f(ir) ≤
f(jr). Es decir, para cada r, el r-ésimo intervalo que selecciona el algoritmo termina al menos tan pronto
como el r-ésimo intervalo en O.

(4.3) El anterior algoritmo retorna un conjunto óptimo A.

➤ La anterior implementación hace que éste algoritmo corra en O(nlogn).

Intervalo de Planificación Particionado

El objetivo es repartir todos los intervalos entre múltiples recursos de forma tal que utilicemos la menor
cantidad de recursos posibles.

Profundidad: Definimos la profunidad de un conjunto de intervalos como el número máximo de veces que
un mismo momento pasa en diferentes intervalos en el tiempo.

(4.4) En cualquier instancia del intervalo de planificación particionado, el número de recursos que se
necesitan es por lo menos la profundidad del conjunto de intervalos.

Algoritmo

Sea d la profundidad del conjunto de intervalos, asignaremos una etiqueta de {1, …, d} a cada intervalo de
forma tal que dos intervalos que se superpongan tengan etiquetas diferentes.

Ordenar los intervalos según sus tiempos de inicialización

Denotar los intervalos I1, …, In en ese orden
For j = 1, …, n
For cada intervalo Ii que comienza antes que Ij y que además superpone a Ij
Excluir la etiqueta de Ii de las posibles etiquetas para Ij
Endfor
If hay alguna etiqueta de {1, …, d} que no ha sido excluída
Asignar una de las etiquetas que no han sido excluídas a Ij
Else
Dejar Ij sin etiqueta
Endif
Endfor

(4.5) Si utilizamos el anterior algoritmo, a cada intervalo se le asignará una etiqueta, y ningún intervalo que
se superponga con otro intervalo tendrá la misma etiqueta que éste.
(4.6) El algoritmo anterior asigna cada intervalo a un recurso, usando una cantidad de recursos igual a la
profundidad del conjunto de intervalos. Éste es el número óptimo de recursos necesitados.

Planificando para Minimizar la Tardanza

Tenemos un único recurso y un conjunto de n solicitudes para usar el recurso por un intervalo de tiempo,
pero en vez de que cada solicitud tenga un tiempo de inicio y finalización, se tiene que la solicitud i tiene un
tiempo límite di, y requiere un intervalo de tiempo contínuo de largo ti, siendo que se puede planificar en
cualquier momento mientras sea antes del tiempo límite.

A cada solicitud se le debe asignar un intervalo de tiempo ti, y diferentes solicitudes no deben
superponerse. Denotaremos el intervalo ti como [s(i),f(i)] con f(i) = s(i) + ti.

Tardanza: Decimos que una solicitud i llega tarde si no cumple con el tiempo límite, es decir, f(i) > di.
La tardanza de una solicitud i la definimos como li = f(i) - di.
li = 0 si la solicitud no llegó tarde.

➤ Objetivo: Minimizar la mayor tardanza L = maxi li.

Algoritmo
Ordenar las solicitudes según su tiempo límite en orden ascendente
Por simplicidad asumir la notación d1 ≤ … ≤ dn
Inicialmente f = s
Considerar las solicitudes i = 1, …, n en este orden
Asignar la solicitud i al intervalo de tiempo comenzando en s(i) = f hasta f(i) = f + ti
Asignamos f = f + ti
End
Return el conjunto de los intervalos planificados [s(i),f(i)] con i = 1, …, n

(4.7) Existe una planificación óptima sin tiempos libres entre las solicitudes.

Inversión: Una planificación A’ tiene una inversión si una solicitud i con tiempo límite di está planificada
antes que otra solicitud j con un tiempo límite menor (dj < di).

(4.8) Todas las planificaciones sin inversiones y sin tiempo libre entre las solicitudes tienen la misma mayor
tardanza.

(4.9) Existe una planificación óptima que no tiene inversiones ni tiempo libre entre solicitudes.

(4.10) La planifiación A producida por el anterior algoritmo tiene una mayor tardanza óptima L.
Los Caminos más Cortos en un Grafo
Largo de un Camino: Dado un camino P, definimos su largo l(P) como la suma de los largos de todas las
aristas en P, donde cada arista e tiene largo le ≥ 0.

➤ Dado un grafo G = (V,E) y un nodo s, queremos el camino más corto comenzando por s hacia todos los
demás nodos.

➤ Adaptación para grafos no-dirigidos: Si tenemos un grafo no-dirigido lo podemos tratar de la siguiente
forma: reemplazamos todas las aristas e = (u,v) de largo le del grafo no dirigido por dos aristas dirigidas
(u,v) y (v,u) con largo cada le una.

Algoritmo Dijkstra
El algoritmo mantiene un conjunto de vértices u, para los cuales hemos determinado un camino desde s lo
más corto posible de distancia d(u), ésa es la parte ‘’explorada’’ del grafo. Inicialmente tenemos S = {s} y
d(s) = 0.

Sea S el conjunto de nodos explorados (por cada u ∈ S, almacenaremos una distancia d(u))
Inicialmente S = {s} y d(s) = 0
While S ≠ V
Seleccionar un nodo v ∉ S con por lo menos una arista e = (u,v) comenzando en un nodo u ∈ S
que
cumpla que d’(v) = d(u) + le es lo más pequeña posible (hay que minimizar le, donde e es la arista que
hace que v se añada a S)
Añadir v a S y definir d(v) = d’(v)
Endwhile

Mientras cada nodo v es añadido al conjunto S, simplemente registramos la arista (u,v) que alcanzó el
valor mínimo d(u) + le.
Para construir P, simplemente empezamos en v, seguimos la arista que almacenamos para v en dirección
opuesta para llegar a u, luego seguimos la arista que almacenamos para u en dirección opuesta hasta su
predecesor, y así sucesivamente hasta llegar al nodo s.

(4.14) Considere el conjunto S en cualquier punto de la ejecución del algoritmo. Para cada u ∈ S, el
camino Pu es un camino s-u lo más corto posible.

➤ El algoritmo no siempre encuentra los caminos más cortos si se cumple que algunas aristas tienen
valores negativos.
Implementación de Dijkstra
Primero mantenemos los valores de la mínima distancia d’(v) = d(u) + le para cada nodo v ∈ V - S, en vez
de calcularlo en cada iteración. Además, mantendremos los nodos de V - S en una cola de prioridad, cuyas
claves serán d’(v), por lo que necesitaremos de las operaciones CambiarClave() y ExtraerMinimo().
➤ Para seleccionar el nodo v que debería ser añadido a S, necesitamos la operación ExtraerMinimo().

➤ Para actualizar las claves, consideraremos una iteración en la cual v es añadido a S, y w ∉ S es un nodo
que permanece en la cola de prioridad. Qué tenemos que hacer para actualizar el valor de d’(w)?:
● Si e’ = (v,w) no es una arista, entonces no tenemos que hacer nada.
● Si (v,w) ∈ E, entonces el nuevo valor de la clave es min(d’(w), d(v) + le’)

(4.15) Usando una cola de prioridad, el algoritmo Dijkstra puede ser implementado en un grafo con n nodos
y m aristas en un tiempo O(m), sumándole el tiempo para n operaciones de ExtraerMinimo() y m
operaciones de CambiarClave().

El Problema del Árbol de Cubrimiento Mínimo

Suponga que tenemos un conjunto V = {v1, …, vn} de localidades, y queremos construir una red de
comunicaciones sobre ellas. La red debería estar conectada (debería haber un camino para cualquier par
de nodos), pero aparte de eso queremos construirla lo más barato posible.

Para ciertos pares (vi,vj), construiremos un link directo entre vi y vj por cierto costo c(vi,vj) > 0. El problema

es encontrar un subconjunto de aristas T ⊆ E de modo que el grafo (V,T) sea conexo, y el costo total ∑ ce
𝑒∊ 𝑇
sea lo menor posible, donde ce representa un costo positivo asociado a una arista e = (vi,vj).

(4.16) Sea T una solución de mínimo costo al problema de la red de comunicaciones. Entonces tenemos
que (V,T) es un árbol.

➤ Si permitimos que algunas aristas tengan costo 0, entonces la solución de mínimo costo puede que
tenga aristas extras (aristas que tienen 0 costo y podrían ser eliminadas opcionalmente). Pero aún en éste
caso, siempre hay una solución de mínimo costo que es un árbol.

Árbol de Cubrimiento: Llamaremos al subconjunto T ⊆ E como un árbol de cubrimiento de G si (V,T) es

un árbol.

Daremos 3 algoritmos que encuentran correctamente un árbol de cubrimiento mínimo.

Algoritmo 1 - Prim
Mantenemos un conjunto S ⊆ V en el cual se construirá el árbol de cubrimiento mínimo. Inicialmente, S =
{s} (s será la raíz del árbol). En cada iteración, le agregamos un nodo v a S de forma tal que minimice el
costo de añadir éste nodo, es decir, mine = (u,v) / u ∈ S ce , por lo que incluimos la arista e = (u,v) al árbol.
Para poder decidir qué nodo v añadir al conjunto S, mantendremos en una cola de prioridad con clave a(v)
/ a(v) = mine = (u,v) / u ∈ S ce para cada nodo v ∈ V - S. Seleccionaremos un nodo con la operación
ExtraerMinimo(), y actualizaremos a(v) con la operación CambiarClave().

(4.22) Usando una cola de prioridad, el Algoritmo de Prim puede ser implementado en un grafo con n
nodos y m aristas en O(m), añadiendo el tiempo para n operaciones de ExtraerMinimo() y CambiarClave().
Algoritmo hecho por mi
Inicialmente S = {s} el cual será la raíz del árbol
Inicializar árbol T vacío
While S ≠ V
Seleccionar un nodo v ∉ S con por lo menos una arista e = (u,v) comenzando en un nodo u ∈ S tal
que el costo ce es lo más pequeño posible (minimizar ce, donde e es la arista que hace que v se
añada a S)
Añadir v a S
Añadir la arista (u,v) al árbol T
Endwhile
Return T

Algoritmo 2 - Kruskal
Comienza sin ninguna arista, y construye el árbol de cubrimiento mínimo insertando aristas de E según el
costo de las aristas en forma creciente. Mientras se recorren las aristas en éste orden, se inserta una arista
e siempre y cuando no genere un ciclo.

Algoritmo hecho por mi

Ordenar las aristas en forma creciente según su costo en una lista F
Inicializar árbol T vacío
Inicializar S como un conjunto de nodos vacío
While S ≠ V
Sea (u,v) la arista de menor costo en F
If (u,v) no genera un ciclo en T
Agregar (u,v) a T
Agregar u y/o v a S
Endif
Eliminar (u,v) de F
Endwhile
Return T
➤ Si utilizamos una cola de prioridad basada en un heap, podemos implementar ExtraerMinimo() y
CambiarClave() en O(logn), por lo que tendrá un tiempo total de O(mlogn).

Algoritmo 3 - Eliminación Inversa

Comienza con el grafo G = (V,E) y eliminamos aristas para reducir su costo. Para cada arista e (ordenadas
decrecientemente según su costo), la eliminamos siempre y cuando su eliminación no produzca que el
grafo se desconecte.

(4.17) Asuma que todas las aristas tienen diferente costo. Sea S cualquier subconjunto de nodos que no es
ni vacío ni igual a V, y sea e = (v,w) la arista de menor costo con un nodo en S y otro nodo en V. Entonces
todo árbol de cubrimiento minimo contiene a ésta arista.

(4.18) El Algoritmo de Kruskal produce un árbol de cubrimiento mínimo de un grafo G.

(4.19) El Algoritmo de Prim produce un árbol de cubrimiento mínimo de un grafo G.

(4.20) Asuma que todas las aristas tienen diferente costo. Sea C cualquier ciclo en G, y sea e = (v,w) la
arista de mayor costo perteneciente a C. Entonces la arista e no pertenece a ningún árbol de cubrimiento
mínimo.

(4.21) El Algoritmo de Eliminación Inversa produce un árbol de cubrimiento mínimo de un grafo G.

➤ Cualquier algoritmo que construya un árbol de cubrimiento incluyendo aristas utilizando (4.17), o lo
construya eliminando aristas según (4.20) (en cualquier orden), entonces terminará construyendo un árbol
de cubrimiento mínimo.

Estructura Simple de Datos Union-Find Para Kurskal

En ésta sección, consideramos un grafo el cual evoluciona agregándole aristas. Es decir, el grafo tiene una
cantidad de nodos fija, pero crece según el tiempo al añadir aristas entre algunos pares de nodos. El
objetivo es mantener registro del conjunto de componentes conexas de ese grafo durante su evolución.

Cada vez que se considera una arista e = (v,w), necesitamos encontrar eficientemente las identidades de
las componentes conexas de v y w. Si éstas componentes son diferentes, entonces no hay un camino de v
a w por lo que e se añadirá al grafo; pero si las componentes son iguales, entonces hay un camino de v a
w con las aristas ya incluidas, por lo que e no se añadirá al grafo.
En el caso de que e es incluída, la estructura de datos debería mezclar eficientemente las componentes de
v y w en una nueva componente.
Ésta estructura tendrá 3 operaciones:
● Para un conjunto S, MakeUnionFind(S) retorna una estructura de Union-Find en el conjunto S, donde
todos los elementos estan en conjuntos diferentes. Por ejemplo, esto corresponde a las componentes
conexas de un grafo sin aristas. Nuestro objetivo es implementarla en O(n), donde |S| = n.
● Dado un nodo u, la operación Find(u) retorna el nombre de la componente conexa de u. Ésta operación
puede ser utilizada para verificar si dos nodos u y v están en el mismo conjunto, simplemente evaluando
 si Find(u) = Find(v). Nuestro objetivo es implementarla en O(logn), aunque algunas implementaciones
permiten un orden O(1).
● La operación Union(A,B) une dos conjuntos A y B en un solo conjunto. Nuestro objetivo es
implementarla en O(logn).

Para realizar esto, mantendremos un arreglo Component de tamaño n (|S| = n), donde Component[s] es el
nombre del conjunto que contiene a s (para nombrar un conjunto, usaremos el nombre de algún elemento
del conjunto). Tambien tendremos una lista de los elementos que pertenecen a cada conjunto, para no
tener que recorrer el arreglo cuando querramos actualizar. Además, mantendremos un arreglo Size de
largo n, donde Size[A] es el tamaño del conjunto A, por lo que cuando querramos ejecutar la operación
Union(A,B) usaremos el nombre del conjunto más grande (para tener que actualizar menos elementos).

(4.23) Considere la implementación de arreglo de Union-Find para algún conjunto S de tamaño n, donde
las uniones mantienen el nombre del conjunto más grande. La operación Find() es O(1), MakeUnionFind()
es O(n), y cualquier secuencia de k operaciones Union() es a lo sumo O(klogk).

➤ En vez de acotar el tiempo en una sola operación de Union(), acotaremos el tiempo total que requiere
actualizar Component[v] para un elemento v durante la secuencia de k operaciones.

Una Mejor Estructura de Datos para Union-Find

Cada nodo v ∈ S estará dentro de un registro, donde el 2do campo es un puntero al nombre del conjunto
del cual pertenece, y el 3er campo contiene la cantidad de elementos del conjunto. Para inicializar
MakeUnionFind(S), habrá un registro para cada elemento v ∈ S, donde el puntero apunta al mismo
elemento (o a null) para indicar que v está en su mismo conjunto.

Considere la Union de dos conjuntos A y B, donde el nombre de A es v (v ∈ A), y el nombre de B es u (u

∈ B). La idea es que la unión de estos dos conjuntos tenga el nombre del conjunto con más elementos,
asumimos que es v. Por lo que simplemente tendremos que actalizar el puntero de u hacia v, sin tener que
modificar los punteros de los otros elementos de B.

(4.24) Considere la implementación de puntero de Union-Find para algún conjunto S de tamaño n, donde
las uniones mantienen el nombre del conjunto más grande. Una operación Union() es O(1),
MakeUnionFind() es O(n) y una operación Find() es O(logn).

Implementación de Kruskal
Primero tenemos que ordenar las aristas según su costo. Ésto toma O(mlogm) = O(mlogn), ya que m ≤ n2.
Luego, usamos la estructura de Union-Find para mantener las componentes conexas de (V,T) mientras se
añaden aristas. Cada vez que consideramos una arista e = (v,w), ejecutamos Find(v) y Find(w) para ver si
v y w pertenecen a la misma componente conexa o no. Ejecutamos Union(Find(v),Find(w)) para unir las
dos componentes, si el algoritmo decide incluir e al árbol T. Haremos un total de a lo sumo 2m operaciones
Find() y n - 1 operaciones Union().

(4.25) El Algoritmo Kruskal puede ser implementado en un grafo de n nodos y m aristas en O(mlogn).
Capítulo 5 - Divide y Vencerás
Divide y vencerás se refiere a una clase de técnicas de algoritmo en la cual uno divide las entradas en
varias partes, resuelve el problema en cada parte recursivamente, y luego combina las soluciones a estos
subproblemas en una solución global.

Algoritmo Mergesort (unión ordenada)

Mergesort ordena una lista dada de números, primero dividiéndola entre dos partes iguales, ordenando
cada mitad usando recursión, y luego combina los resultados de éstas llamadas recursivas (en la forma de
dos mitades ordenadas), usando un algoritmo lineal dado en el capítulo 2.
Necesitaremos un caso base ya que estamos utilizando recursión. En éste caso, asumiremos que una vez
que la entrada se haya reducido a 2 elementos, pararemos la recursión y ordenaremos los elementos
simplemente comparándolos entre sí.

Abstraeremos el comportamiento en el siguiente modelo, que describe varios algoritmos del tipo
divide-y-conquistaras:

(✝) Dividir la entrada en dos partes iguales, resolver los dos subproblemas en éstas partes usando
recursión, y luego combinar los dos resultados en una solución global, pasando únicamente tiempo lineal
para la división inicial y la combinación final.

(5.1) Considerando el patrón (✝) se tiene que, para alguna constante c T(n) ≤ 2T(n/2) + cn cuando n > 2, y
además T(2) ≤ c.Más formalmente: T(n) ≤ 2T(n/2) + O(n).

➤ Seguiremos los siguientes pasos para resolver las recursiones: Analizar unos primeros niveles,
identificar un patrón y sumando todos los niveles de recursión. Tambien se puede adivinar la solución,
sustituirla en la relación de la recurrencia y ver si funciona.

Resolviendo la Recurrencia de Mergesort

● Analizando los primeros niveles: En el primer nivel de la recursión, tenemos un único problema de
tamaño n, que a lo sumo toma un tiempo de cn, más el tiempo en todas las siguientes recursiones. En
el siguiente nivel, tenemos dos problemas de tamaño n/2 cada uno. Éstos demoran a lo sumo cn/2 cada
uno, por lo que se tiene un total de a lo sumo cn, más el tiempo en todas las siguientes recursiones. En
el tercer nivel, se tienen cuatro problemas de tamaño n/4 cada uno. Éstos demoran a lo sumo cn/4 cada
uno, por lo que se tiene un total de a lo sumo cn.
● Identificación de Patrón: En general, en un nivel j de recursión, el número de subproblemas se ha
duplicado j veces, por lo que ahora hay 2j. Cada uno ha disminuido su tamaño por un factor de 2 j
veces, llegando a un tamaño de n/2j, por lo que cada uno demora a lo sumo cn/2j. Por lo que el tiempo
de j es de un total de a lo sumo 2j(cn/2j) = cn.
● Sumando todos los Niveles: Hemos descubierto que la recurrencia en (5.1) tiene la propiedad de que
la misma cota superior cn aplica al trabajo total en cada nivel. El número de veces que la entrada deba
ser dividida en dos para reducir su tamaño de n a 2 es log2 n. Por lo que sumando los cn de log2 n
niveles, tenemos un total de O(nlogn)
(5.2) Cualquier función T(.) que satisfaga (5.1) está acotada por O(nlogn), cuando n > 1.

➤ Si queremos adivinar el tiempo en el que el algoritmo corre en nlogn lo haremos de la siguiente manera:
Suponemos que creemos que T(n) ≤ cnlog2 n para todo n ≥ 2, y queremos comprobar si es verdad o no.
Ésto claramente se cumple para n = 2, ya que en éste caso cnlog2 n = 2c, y (5.1) nos dice explícitamente
que T(2) ≤ c. Ahora suponga por inducción que T(m) ≤ cmlog2 m para todo m < n, y queremos comprobar
esto para T(n). Haremos esto escribiendo la recurrencia para T(n) sustituyendolo en la inecuación
T(n/2) ≤ c(n/2)log2 (n/2). Luego simplificaremos la expresión resultante notando que log2 (n/2) = (log2 n) - 1.
Por lo que tendremos lo siguiente:
T(n) ≤ 2T(n/2) + cn
T(n) ≤ 2c(n/2)log2 (n/2) + cn
T(n) ≤ cn[(log2 n) - 1] +cn
T(n) ≤ (cnlog2 n) -cn +cn
T(n) ≤ cnlog2 n

Ésto establece la cota que queremos para T(n), asumiendo que se cumple para valores menores que n, y
esto completa nuestro argumento inductivo.

➤ Si queremos calcular un acercamiento usando sustitución parcial lo haremos de la siguiente manera:

Suponga que creemos que T(n) = O(nlogn), pero no estamos seguros de la constante dentro de la notación
de O(.). Podemos usar el método de sustitución aunque ni siquiera estemos seguros de ésta constante.
Primero escribimos T(n) ≤ knlogb n para alguna constante k y base b que determinaremos luego. Ahora
queremos saber si hay alguna opción de k y b que funcionen en un argumento inductivo, por lo que
intentaremos un nivel de inducción como sigue:
T(n) ≤ 2T(n/2) + cn ≤ 2k(n/2)logb(n/2) +cn
Utilizando b = 2 (ya que log2 (n/2) = (log2 n) - 1), tenemos que:
T(n) ≤ 2k(n/2)log2(n/2) +cn
T(n) ≤ 2k(n/2)[(log2n) - 1] +cn
T(n) ≤ kn[(log2n) - 1] +cn
T(n) ≤ (knlog2n) - kn +cn
Finalmente preguntamos: Hay alguna opción de k que cause que la última expresión sea acotada por
knlog2n? La respuesta es sí, sólo tenemos que elegir algún k que sea por lo menos tan grande como c, por
lo que obtenemos:
T(n) ≤ (knlog2n) - kn +cn ≤ knlog2n
Ésto completa la inducción.
Llegamos a la conclusión de que el método de sustitución puede ser útil cuando tratamos de encontrar las
constantes exactas, cuando uno tiene una idea de la forma general de la solución.

Más Relaciones en la Recurrencia

Una clase de algoritmos más general de divide y conquistarás consiste en llamadas recursivas en q
subproblemas de tamaño n/2, y luego combina los resultados en O(n).
(5.3) Sea T(n) el tiempo de ejecución de un algoritmo del estilo anterior, entonces tenemos que para
alguna constante c, T(n) ≤ qT(n/2) + cn cuando n > 2, y además T(2) ≤ c.

Caso 1: q > 2 Subrproblemas

● Analizando los Primeros Niveles: En el primer nivel de recursión tenemos un único problema de
tamaño n, el cuál demora como mucho cn más el tiempo en todas las siguientes llamadas recursivas.
En el siguiente nivel, tenemos q subproblemas de tamaño n/2 cada uno. Cada uno de ellos toma como
mucho cn/2, por lo que demoran un total de (q/2)cn más el tiempo de todas las siguientes llamadas
recursivas. El siguiente nivel tiene q2 problemas, cada uno de tamaño n/4, lo que llevará un tiempo total
de (q2/4)cn. Como q > 2, el trabajo total por nivel va aumentando a medida que avanzamos en la
recursión.
● Identificando un Patrón: Al alcanzar el nivel j, tenemos qj instancias distintas, cada una de tamaño n/2j.
Por lo que el trabajo total en el nivel j es qj(cn/2j) = (q/2)jcn.
● Sumando Todos los Niveles de Recursión: Tenemos log2 n niveles de recursión, y la cantidad total de
trabajo es la suma sobre todos los niveles:
𝑙𝑜𝑔2 (𝑛−1) 𝑙𝑜𝑔2 (𝑛−1)
T(n) ≤ ∑ (q/2)jcn = cn ∑ (q/2)j
𝑗=0 𝑗=0

Ésto es una suma geométrica, por lo que usaremos su fórmula cuando r > 1 (r = q/2)
T(n) ≤ cn (rlog2 n - 1/r - 1) ≤ cn (rlog2 n/r - 1)
Sacamos las constantes para afuera
T(n) ≤ (c/r - 1)nrlog2 n
Con la propiedad alog b = blog a para a > 1 y b > 1 se tiene que
rlog2 n = nlog2 r = nlog2 (q/2) = n(log2 q) - 1
Por lo que llegamos a
T(n) ≤ (c/r - 1)n.n(log2 q) - 1 ≤ (c/r - 1)n(log2 q) = O(n(log2 q) )
(5.4) Cualquier función T(n) que satisfaga (5.3) con q > 2 es O(n(log2 q))

Caso 2: q = 1
● Analizando los Primeros Niveles: En el primer nivel de recursión, tenemos un único problema de
tamaño n, que demora como mucho cn más el tiempo en todas las siguientes llamadas recursivas. En el
siguiente nivel tenemos un problema de tamaño n/2, el cual demora cn/2; y el siguiente nivel tiene un
problema de tamaño n/4, el cual demora cn/4. Al contrario del caso anterior, el trabajo total por nivel va
decreciendo a medida que procedemos con la recursión.
● Identificando un Patrón: Al alcanzar el nivel j, tenemos solamente una instancia de tamaño n/2j, por lo
que tiene un tiempo de cn/2j.
● Sumando Todos los Niveles de Recursión: Hay log2 n niveles de recursión, y la cantidad total de
trabajo es la suma sobre todos estos niveles:
𝑙𝑜𝑔2 (𝑛−1) 𝑙𝑜𝑔2 (𝑛−1)
T(n) ≤ ∑ cn/2j = cn ∑ 1/2j
𝑗=0 𝑗=0

Ésta suma converge a 2 (aún yendo hasta el infinito) por lo que tenemos que
 T(n) ≤ 2cn = O(n)
(5.5) Cualquier función T(n) que satisfaga (5.3) con q = 1 es O(n)

T(n) ≤ 2T(n/2) + O(n2)

Tiene la siguiente estructura:

Dividir la entrada en 2 partes iguales, resolver los dos subproblemas de éstas partes por recursión, y luego
combinar los dos resultados en una solución global, pasando tiempo cuadrático entre la división inicial y la
combinación final.

(5.6) Para alguna constante c, T(n) ≤ 2T(n/2) + cn2 cuando n > 2 y T(2) ≤ c.

● Analizando los Primeros Niveles: En el primer nivel de recursión, tenemos un único problema de
tamaño n, que demora como mucho cn2 más el tiempo en todas las siguientes llamadas recursivas. En
el siguiente nivel tenemos dos problemas de tamaño n/2, los cuales demoran c(n/2)2 = cn2/4, por un total
de a lo sumo cn2/2 más el tiempo en las siguientes llamadas recursivas. En el tercer nivel, tenemos
cuatro problemas de tamaño n/4, por lo que cada uno demora c(n/4)2 = cn2/16, por un total de a lo sumo
cn2/4.
● Identificando un Patrón: Al alcanzar el nivel j, tenemos 2j subproblemas de tamaño n/2j cada uno, por
lo que el trabajo total en éste nivel es 2jc(n/2j)2 = cn2/2j.
● Sumando Todos los Niveles de Recursión: Hemos llegado a la misma sumatoria que el caso q = 1,
sólo que en vez de n tenemos n2, por lo que:
𝑙𝑜𝑔2 (𝑛−1) 𝑙𝑜𝑔2 (𝑛−1)
T(n) ≤ ∑ cn2/2j = cn2 ∑ 1/2j ≤ 2cn2 = O(n2)
𝑗=0 𝑗=0

Contando Inversiones
Consideraremos un problema que surge en los análisis de los rankings. Por ejemplo, algunos sitios web
utilizan la técnica llamada ‘’filtración colaborativa’’, en la cual ellos tratan de emparejar tus preferencias
(para libros, películas, restaurantes) con las preferencias de otra gente en internet. Una vez que el sitio
web ha definido gente con gustos ‘’similares’’ a los tuyos (basados en la comparación de tus preferencias
con las de las demás personas), puede recomendar cosas nuevas que a éstas demás personas les han
gustado.
Vamos a comparar tu ranking con el de otra persona sobre el mismo conjunto de n películas. Un método
natural sería etiquetar las películas del 1 al n según tú ranking, y luego ordenar éstas etiquetas según el
ranking de la otra persona y ver cuántos pares están ‘’fuera de orden’’. Más concretamente,
consideraremos el siguiente problema:

➤ Nos dan una secuencia de n números a1, …, an (asumiremos que todos los números son distintos).
Queremos definir una medida que nos diga qué tan lejos está la lista de estar en orden ascendiente, el
valor de la medida debería ser 0 si a1< a2 < …< an, y debería aumentar a medida que los números se
mezclan más.
Inversión: Decimos que dos índices i < j forman una inversión si ai > aj, eso sucede si los dos elementos ai
y aj están fuera de lugar.

Para determinar el número de inversiones en una secuencia a1, …, an, dibujaremos la secuencia en el
orden que nos la han dado, y debajo la secuencia en orden ascendente. Luego trazaremos una línea entre
cada número de la secuencia de arriba con su copia en la secuencia de abajo. Cada línea que se
intersecte con otra corresponde a un par de elementos que está en diferente orden entre las 2 listas, en
otras palabras, una inversión.

Merge-and-Count (A, B) (Unir-y-Contar)

Suponga que las listas A y B vienen de dividir un ranking R en dos, donde |R| = n y m = n/2, por lo que
tenemos la lista A = a1, …, am y B = am+1, …, an que además han sido ordenadas y tienen sus inversiones
contadas. Queremos producir una única lista C ordenada uniendo éstas dos listas, mientras que tambien
contamos los pares (a,b) con a ∊ A, b ∊ B y a > b. Como A y B están ordenadas de menor a mayor,
podremos contar las invsersones fácilmente. Cada vez que un elemento ai se añade a C no hay nuevas
inversiones, ya que ai es más pequeño que todo lo que queda en la lista B, y además va antes que todos
esos elementos. Por otro lado, si bi es añadido a C, entonces es más pequeño que todos los elementos
que quedan en A y además va luego que todos esos elementos, por lo que a nuestro contador de
inversiones le sumamos la cantidad de elementos que quedan en A.

Inicializar C como una lista vacía

Mantener un puntero current en ambas listas, inicialmente cada uno apunta al primer elemento de su lista
Mantener una variable count para el número de inversiones, inicialmente está en 0
While las dos listas tengan elementos
Sean ai y bj los elementos apuntados por el puntero current
Añadir el elemento más pequeño a C
If bj es el elemento más pequeño
Sumarle a count la cantidad de elementos que quedan en la lista A
Endif
Avanzar el puntero current en la lista en la cual el elemento más pequeño fue seleccionado
Endwhile
Una vez que una lista está vacía, agregar los elementos que quedan de la otra lista a C
Return count y la lista C

➤ Cada iteración del while toma tiempo constante, y en cada iteración añadimos un elemento a la lista de
salida que no se verá de nuevo. Por eso, el número de iteraciones puede ser como mucho la suma de los
largos iniciales de A y B, por lo que es O(n).
Sort-and-Count (L) (Ordenar-y-Contar) - Recursivo
If la lista tiene un elemento
No hay inversiones
Else
Dividir la lista en dos mitades:
A contiene los primeros n/2 elementos (redondeado hacia arriba)
B contiene los n/2 elementos restantes (redondeado hacia abajo)
(rA, A) = Sort-and-Count(A)
(rB, B) = Sort-and-Count(B)
(r, L) = Merge-and-Count(A, B)
Endif
Return r = rA + rB + r y la lista ordenada L

➤ Como Merge-and-Count toma O(n), el T(n) total de Sort-and-Count satisface (5.1), por lo que por (5.2)
tenemos:

(5.7) El algoritmo Sort-and-Count ordena la entrada y cuenta las inversiones correctamente en O(nlogn)
para una lista de n elementos.

Encontrando el Par Más Cercano de Puntos

Denotemos el conjunto de puntos P = (p1, …, pn), donde pi tiene coordenadas (xi,yi) y para dos puntos pi y
pj ∈ P utilizamos d(pi,pj) para denotar la distancia euclidiana entre ellos (√(xi - xj)2 + (yi - yj)2). Nuestro
objetivo es encontrar el par de puntos pi,pj que minimice d(pi,pj).

Nuestro plan será aplicar el estilo de Divide y Vencerás de Mergesort: encontraremos el par más cercano
entre los puntos de la ‘’mitad izquierda’’ de P, y el par más cercano entre los puntos de la ‘’mitad derecha’’
de P, donde finalmente usaremos esa información para llegar a una solución global en tiempo linear.

Armando la Recursión
Será bastante útil si en cada llamada recursiva en un conjunto P’ ⊆ P, comienza con dos listas: una lista
P’x en la cual todos los puntos en P’ han sido ordenados según la coordenada de x en orden creciente; y
una lista P’y en la cual todos los puntos en P’ han sido ordenados según la coordenada de y en orden
creciente. Podemos asegurar que esto permanece verdadero durante el algoritmo de la siguiente forma:
Primero, antes de que cualquier recursión comience, producimos las listas Px y Py de P. En cada elemento
de ambas listas habrá un registro que mantendrá al punto como tal y la posición en la que se encuentra
ese punto en cada lista.

En el primer nivel de recursión, Definimos Qx como el conjunto de puntos en los primeros n/2 elementos
(redondeado hacia arriba) de la lista Px, y el conjunto Rx como el conjunto de puntos en los demás n/2
(redondeado hacia abajo) elementos en la lista Px. Luego, para construir Qy y Ry toma el x máximo en Qx y
en base a ese x recorre Py poniendo en Qy los puntos que cumplen con ese x máximo, y luego toma el x
mínimo en Rx y en base a ese x pone en Ry los puntos que cumplen con ese x mínimo (lo hace en
simultáneo para no recorrer 2 veces).

Combinando las Soluciones

Sea δ el mínimo de d(q*0,q*1) y d(r*0,r*1). La pregunta es: Hay algún punto q ∈ Q y r ∈ R donde d(q,r) < δ?
Si no lo hay, entonces hemos encontrado el par más cercano de puntos en las llamadas recursivas. Pero si
lo hay, entonces el par más cercano es q y r.

Denotaremos x* como la coordenada x del punto más a la derecha en Q, y denotaremos L la línea vertical
descrita por la ecuación x = x*. Ésta línea separa Q de R.

(5.8) Si existe q ∈ Q y r ∈ R tal que d(q,r) < δ, entonces tanto q como r se encuentran entre una distancia
δ de L.

Por lo que si queremos encontrar los puntos q y r, podemos restringir nuestra búsqueda a los puntos en P
que estén a una distancia de a lo sumo δ (dice narrow band? se referirá a los puntos que su coordenada
de x esté a lo sumo de una distancia δ?). Sea S ⊆ P el conjunto de puntos que cumplen eso, y sea Sy la
lista de puntos en S ordenados según su coordenada y. Por una única pasada en Py podemos construir Sy
en O(n).

(5.9) Existen q ∈ Q y r ∈ R tal que d(q,r) < δ si y solo sí existen s y s’ tal que d(s,s’) < δ.

(5.10) Si s, s’ cumplen que d(s,s’) < δ, entonces s y s’ están en 15 posiciones entre sí en la lista ordenada
Sy.

Concluímos el algoritmo como sigue: Recorremos una vez Sy, y por cada s ∈ Sy, computamos la distancia
a cada uno de los siguientes 15 puntos en Sy. (5.10) implica que si hacemos eso, hemos computado la
distancia de cada par de puntos en S (si existe alguno) que se encuentran a una distancia menor a δ.
Habiendo hecho esto, podemos comparar la distancia mínima con δ, declarando una de las dos siguientes
cosas:

1. El par más cercano de puntos en S, si su distancia en menor que δ.

2. La conclusión correcta de que no hay par de puntos en S cuya distancia sea menor a δ.

En caso que suceda lo primero, éste par es el par más cercano en P. Por el contrario, el par encontrando
en nuestras llamadas recurisvas es el par más cercano de puntos en P.

Algoritmo
Closest-Pair(P):
Construir Px y Py (O(nlogn))
(p*0, p*1) = Closest-Pair-Rec(Px,Py)
Closest-Pair-Rec(Px,Py):
If |P| ≤ 3
Encontrar el par más cercano midiendo todas las distancias
Endif

Construir Qx, Qy, Rx, Ry (O(n))

(q*0, q*1) = Closest-Pair-Rec(Qx,Qy)
(r*0, r*1) = Closest-Pair-Rec(Rx,Ry)

δ = min(d(q*0, q*1), d(r*0, r*1))

x* = coordenada máxima de x en Q
L = {(x,y) : x = x*}
S = puntos en P que están a lo sumo a una distancia δ de L

Construir Sy (O(n))
For each punto s ∈ Sy, calcular la distancia de s a cada uno de los siguientes 15 puntos en Sy
Sea s, s’ el par con la mínima de éstas distancias (O(n))

If d(s,s’) < δ
Return (s,s’)
Else if d(q*0, q*1) < d(r*0, r*1)
Return (q*0, q*1)
Else
Return (r*0, r*1)
Endif

(5.11) El algoritmo devuelve correctamente el par más cercano de puntos en P.

(5.12) El algoritmo corre en O(nlogn)

Multipliacación de Enteros

El análisis del algoritmo más rápido usará una de las recurrencias consideradas en 5.2, en la cual hay
más de 2 llamadas recursivas en cada nivel.

Consideraremos la multiplicación de 2 enteros de la forma que enseñan en la escuela. Consiste en un

algoritmo que multiplica dos números de n dígitos x e y. Primero se computa un ‘’producto parcial’’ que
consiste en multiplicar separadamente cada dígito de y por x, y luego suma todos los productos parciales.
Asumiremos que estamos trabajando en base-2 (aun que en realidad no importa), y empezaremos por
escribir x como x1.2n/2 + x0. En otras palabras, x1 corresponde al ‘’orden mayor’’ n/2 bits, y x0 corresponde
al ‘’orden menor’’ n/2 bits. Análogamente escribiremos y = y1.2n/2 + y0. Tenemos que:

xy = (x1.2n/2 + x0)(y1.2n/2 + y0)

xy = x1y1.2n + (x1y0 + x0y1).2n/2 + x0y0

La anterior ecuación reduce el problema de resolver una única instancia de n bit (multiplicando los 2
números de n bit x e y) al problema de resolver cuatro instancias de n/2 bit (computando los productos
x1y1, x1y0 , x0y1 , x0y0). La combinación de las soluciones requiere un número constante de adiciones de
O(n) bit, por lo que toma O(n). Por esto, el tiempo de ejecución T(n) está acotado por la siguiente
recurrencia:
T(n) ≤ 4T(n/2) +cn
Para alguna constante c.

Podemos observar que es el caso de q = 4 en los tipos de recurrencias que vimos anteriormente, por lo
que tendremos un tiempo T(n) ≤ O(nlog2 (q)) = O(n2). Debemos usar una estrategia con tres llamadas
recursivas (q = 3) para mejorar el tiempo cuadrático, lo que nos llevará a T(n) ≤ O(nlog2 (q)) = O(n1,59).

El truco es considerar el resultado de una única multiplicación (x1 + x0)(y1 + y0) = x1y1 + x1y0 + x0y1 + x0y0.
Ésto contiene los cuatro productos de más arriba sumados entre sí, por el costo de una única
multiplicación recursiva. Si ahora determinamos x1y1 y x0y0 por recursión, luego de obtenerlos podemos
obtener los otros términos substrayendo x1y1 y x0y0 de (x1 + x0)(y1 + y0).

Algoritmo
Multiplicar-Recursivo(x,y)
Escribir x = x1.2n/2 + x0, y = y1.2n/2 + y0
Computar x1 + x0 y y1+ y0
p = Multiplicar-Rescursivo(x1 + x0,y1+ y0)
x1y1 = Multiplicar-Rescursivo(x1,y1)
x0y0 = Multiplicar-Rescursivo(x0,y0)
Return x1y1.2n + (p - x1y1 - x0y0).2n/2 + x0y0

Dados 2 n-bits números, realiza un número constante de adiciones en O(n)-bits números, sumándole las 3
llamadas recursivas. Por lo que ahora tenemos T(n) ≤ 3T(n/2) +cn para alguna constante c.

(5.13) El tiempo de ejecución de Multiplicar-Recursivo en dos factores de n-bits es O(nlog2 (3)) = O(n1,59).
Capítulo 6 - Programación Dinámica
Es una técnica de diseño de algoritmos. Su idea básica parte desde la intuición detrás de
divide-y-vencerás, y es esencialmente lo opuesto a la estrategia de los algoritmos codiciosos: uno
implícitamente explora el espacio de todas las posibles soluciones, descomponiendo cuidadosamente las
cosas en una serie de subproblemas; y luego construye la solución correcta para subproblemas más y más
grandes. Aunque está trabajando sistemáticamente entre las posibles soluciones exponenciales que hayan
para el problema, lo hace sin examinar a todas explícitamente.

Intervalo de Planificación con Valor (Weighted Interval Scheduling)

Está descrito en el capítulo 1.

Empezaremos nuestra introducción a la programación dinámica con un algoritmo recursivo para éste
problema, y luego moveremos a un método más iterativo que se asemeja al estilo de algoritmos que
usamos en éste capítulo.

Tenemos n solicitudes etiquetadas del 1 al n, donde cada solicitud i especifica un tiempo de comienzo si y
un tiempo de finalización fi. Cada intervalo i además tiene un valor vi. Dos intervalos son compatibles si no
se solapan en el tiempo.
El objetivo es seleccionar un subconjunto S ⊆ {1, …, n} de intervalos mutuamente compatibles, que a su
vez maximice la suma de los valores de los intervalos seleccionados.

Supongamos que las solicitudes están ordenadas en orden creciente según el tiempo de finalización:
f1 ≤ f2 ≤ … ≤ fn. Definimos p(j) para un intervalo j como el mayor índice i que cumple que i < j y además los
intervalos i y j son disjuntos. Definimos p(j) = 0 si ninguna solicitud i < j es disjunta de j.

Para cualquier valor j entre 1 y n, denotamos Oj como la solución óptima al problema que consiste de las
solicitudes {1, …, n}, y denotaremos OPT(j) como el valor de ésta solución. (Definimos OPT(0) = 0, basado
en la convención de que éste es el valor óptimo sobre un conjunto vacío de intervalos).
Podemos decir que si j ∈ Oj entonces OPT(j) = vj + OPT(p(j)), y en caso contrario (j ∉ Oj) se tiene que
OPT(j) = OPT(j-1).

(6.1) OPT(j) = max(vj + OPT(p(j)), OPT(j-1)).

(6.2) La solicitud j pertenece a una solución óptima sobre el conjunto {1, …, j} si y sólo sí se cumple que:
vj + OPT(p(j)) ≥ OPT(j-1)

Éstos hechos forman la primer componente crucial en la cual una solución es basada en programación
dinámica: una ecuación de recurrencia que exprese la solución óptima (o su valor) en términos de la
solución óptima para subproblemas más pequeños.
Lo que dice el enunciado (6.1) directamente nos da un algoritmo recursivo para computar OPT(n),
asumiendo que ya hemos ordenado las solicitudes según su tiempo de finalización y computado los
valores p(j) para cada j.
 Algoritmo Recursivo
Compute-Opt(j):
If j = 0
Return 0
Else
Return max(vj + Compute-Opt(p(j)), Compute-Opt(j-1))
Endif

(6.3) Compute-Opt(j) computa correctamente OPT(j) para cada j = 1, 2, …, n (se demuestra por inducción
en j).

➤ Si se implementa exactamente como se describió anteriormente, demora un tiempo exponencial en

ejecutarse en el peor caso.

Memorizando la Recursión
Nuestro algoritmo recursivo Compute-Opt resuelve n+1 subproblemas diferentes, Compute-Opt(0),
Compute-Opt(1), …, Compute-Opt(n). El hecho de que su tiempo de ejecución sea exponencial se debe a
la redundancia en la cantidad de veces que son ejecutadas éstas llamadas.

Podemos eliminar ésta redundancia almacenando el valor de Compute-Opt en un lugar globalmente

accesible la primera vez que lo computamos, y luego simplemente usar éste valor precomputado en lugar
de todas las futuras llamadas recursivas.

Implementamos la anterior estrategia en el siguiente procedimiento M-Compute-Opt. Éste procedimiento

hará uso de un arreglo M[0 … n]; M[j] comenzará con el valor ‘’vacío’’, pero luego almacenará el valor
M-Compute-Opt(j) apenas sea determinado. Para determinar OPT(n) invocaremos M-Compute-Opt(n).

M-Compute-Opt(j):
If j = 0
Return 0
Else if M[j] no es vacío entonces
Return M[j]
Else
Definir M[j] = max(vj + M-Compute-Opt(p(j)), M-Compute-Opt(j-1))
Return M[j]
Endif

(6.4) M-Compute-Opt es ejecutado en O(n), asumiendo que los intervalos de entrada están ordenados
según su tiempo de finalización.

Hasta ahora hemos computado el valor de una solución óptima, probablemente querramos computar el
conjunto óptimo de intervalos tambien.
A partir de (6.2) sabemos que j pertenece a una solución óptima para el conjunto {1, …, j} si y solo sí se
cumple que vj + OPT(p(j)) ≥ OPT(j-1). Usando ésta observación obtenemos el siguiente procedimiento, el
cual rastrea a través del arreglo M el conjunto solución de intervalos óptimo.

Find-Solution(j):
If j = 0
Return conjunto vacío
Else
If vj + M[p(j)] ≥ M[j-1]
Return j sumándole la solución de Find-Solution(p(j))
Else
Return el resultado de Find-Solution(j-1)
Endif
Endif

(6.5) Dado el arreglo M de la solución de valores óptimos de los subproblemas, Find-Solution retorna un
conjunto solución óptimo en O(n).

Algoritmo Iterativo
Sabemos que M[n] contiene el valor de la solución óptima sobre la instancia total, y Find-Solution puede
ser utilizado para rastrear eficientemente a través de M y retornar el conjunto de intervalos óptimo.

El punto es que podemos computar directamente las entradas de M dado un algoritmo iterativo, en vez de
utilizar recursión memorizada. Simplemente empezamos con M[0] = 0 e incrementamos j hasta llegar a n,
donde cada vez que tengamos que determinar el valor de M[j], la respueta estará dada por (6.1).

Iterative-Compute-Opt:
M[0] = 0
For j = 1, …, n
M[j] = max(vj + M[p(j)], M[j-1])
Endfor

Luego ejecutamos Find-Solution para obtener el conjunto de solución óptima.

➤ Iterative-Compute-Opt es ejecutado en O(n).

Segmentos en Mínimos Cuadrados: Multi-Opciones

En la sección anterior, desarrollamos una recurrencia basada en una opción binaria: el intervalo n
pertenecía a una solución óptima o no. En el problema que consideramos aquí, la recurrencia incolucrará
lo que podría ser llamado ‘’multi-opciones’’: en cada paso, tenemos un número polinómico de posibilidades
a considerar para la estructura de a solución óptima. Como veremos más adelante, un enfoque con
programación dinámica se adapta a ésta situación general naturalmente.

Suponga que nuestra información consiste en un conjunto P de n puntos en el plano denotados (x1,y1),
(x2,y2), …, (xn,yn); y suponga x1 < x2 < … < xn.

Dada una recta L definida por la ecuación y = ax + b, definimos el error de L respecto a P como:
𝑛
Error(L,P) = ∑ (yi - axi - b)2.
𝑖=1

La recta de mínimo error es y = ax + b donde:

a = n.∑xiyi - (∑xi)(∑yi ) ÷ n.∑xi2 - (∑xi)2

𝑖 𝑖 𝑖 𝑖 𝑖

b =( ∑yi - a∑xi ) ÷ n
𝑖 𝑖

Tendremos información en la cual quisiéramos aproximar nuestros puntos a 2 o más líneas. Cómo
podemos formalizar éste concepto? Dado ésto, necesitamos la formulación de un problema que requiera
que adaptemos los puntos bien, es decir utilizando la menor cantidad de rectas posibles.

Segmento: Es un subconjunto de P que representa un conjunto contínuo de puntos según la coordenada

x. Es decir, {pi, pi+1, …, pj-1, pj} para algunos índices i ≤ j.

Entonces para cada segmento S en nuestra partición sobre P, computamos la recta que minimiza el error
con respecto a los puntos en S, siguiendo las fórmulas anteriores.

Multa de una Partición: Está definida por la suma de los siguientes términos:
1. El número de segmentos en los que dividimos P, multiplicado por un factor dado fijo C > 0
2. Por cada segmento, el valor del error de la recta óptima que pasa por ese segmento de
puntos.

Nuestro objetivo es encontrar una partición con mínima multa.

Por ejemplo, al aumentar el número de segmentos, reducimos la multa en el punto 2 de la definición, pero
aumentamos el término en la parte 1 (El factor C es dado con la entrada, y al afinarlo podemos penalizar el
uso de rectas adicionales a una mayor o menor medida).

➤ La siguiente observación es bastante útil: el último punto pn pertenece a un único segmento en la

partición óptima, y ese segmento comienza en algun punto anterior pi. Éste es el tipo de observación que
puede sugerir el conjunto correcto de subproblemas: si supiéramos la identidad del último segmento pi,..,pn,
entonces podríamos remover esos puntos y recursivamente resolver el problema para los puntos restantes
p1, …, pi-1.
Suponga que OPT(i) denota la solución óptima par los puntos p1, …, pi, y sea ei,j el error mínimo de
cualquiera de las rectas respecto a los puntos pi, …, pj. (Escribiremos OPT(0)= 0 como un caso borde).
Entonces tenemos lo siguiente:
(6.6) Si el último segmento de la partición óptima es pi, …, pn, entonces el valor de la solución óptima es
OPT(n) = ei,n + C + OPT(i-1).

(6.7) Para el subproblema en los puntos p1, …,pj, OPT(j) = min1≤i≤j(ei,j + C + OPT(i-1)), y el segmento pi, …,
pj es usado en una solución óptima para el subproblema si y sólo sí el mínimo es obtenido usando el índice
i.

Algoritmo
Segmented-Least-Squares(n):
Arreglo M[0 … n]
Setear M[0] = 0
For all pares i ≤ j
Computar el mínimo error ei,j para el segmento pi, …, pj
Endfor
For j = 1, …, n
Usar la recurrencia (6.7) para computar M[j]
Endfor
Return M[n]

A través del arreglo M podemos rastrear una partición óptima.

Find-Segments(j):
If J = 0
Return conjunto vacío
Else
Encontrar un i que minimice ei,j + C + M[i-1]
Return el segmento {pi, …, pj} y el resultado de Find-Segments(i-1)
Endif

➤ El tiempo para computar todos los errores ei,j es O(n3), aunque es posible reducirlo a O(n2). Dado esto,
una vez que tenemos computados todos los errores, el algoritmo corre en O(n2).

Subconjunto Sumas y Mochilas: Añadiendo una Variable

En ésta sección, consideramos una versión del segundo tipo de problema con duraciones y tiempos
límites, lo que es difícil de resolver usando directamente las técnicas que hemos visto hasta ahora.
Usaremos programación dinámica para resolver el problema, pero con algo nuevo: el conjunto ‘’obvio’’ de
subproblemas no alcanzará, por lo que terminaremos creando una colección más grande de
subproblemas.
En el problemade planificación que consideramos aquí, tenemos una única máquina que puede procesar
trabajos, y tenemos un conjunto de solicitudes {1, …, n}. Únicamente podemos usar la máquina por un
período entre 0 y W, para algún número W. Cada solicitud i corresponde a un trabajo que requiere un
tiempo wi para procesarse. Si nuestro objetivo fuese procesar los trabajos de forma tal que mantengamos
la máquina lo más ocupada posible antes del ‘’corte’’ W, qué trabajos elegiríamos?.

Más formal, tenemos n solicitudes {1, …, n} y cada una tiene un peso dado no negativo wi. También nos
dan el tiempo límite W. Nos gustaría seleccionar un subconjunto S de las solicitudes de forma tal que

∑ wi ≤ W y que sujeto a ésta restricción se tenga que ∑ wi es lo más grande posible.

𝑖∈𝑆 𝑖∈𝑆

➤ Recordar los principios más importantes de la programación dinámica: Se nos tiene que ocurrir un
número pequeño de subproblemas, de forma tal que cada subproblema puede ser resuelto fácilmente a
partir de subproblemas más pequeños aún; y la solución al problema original puede ser fácilmente
obtenida una vez que sabemos las soluciones para todos los subproblemas. Lo complicado aquí es
descubrir un buen conjunto de subproblemas.

Usaremos OPT(i) para denotar la mejor solución posible usando el subconjunto de solicitudes {1, …, i}.
Para encontrar el peso para OPT(n) no solo necesitamos el peso para OPT(n-1), sino que tambien
necesitamos saber la mejor solución que podemos conseguir utilizando un subconjunto de las primeras n-1
solicitudes y el peso total permitido W - wn. Por esto estaremos utilizando más subproblemas: uno por cada
conjunto inicial {1, …, i} de solicitudes, y cada posible valor para el peso restante disponible w. Asumamos
que W es un entero, y que todas las solicitudes i = 1, …, n tienen pesos enteros wi. Tendremos un
subproblema por cada i = 0, 1, …, n y cada 0 ≤ w ≤ W. Usaremos OPT(i,w) para denotar el peso de la
solución óptima utilizando un subconjunto de solicitudes {1, …, i} con el mayor peso permitido w, eso es:

OPT(i,w) = maxS ∑ wj, dónde el máximo está entre subconjuntos S ⊆ {1, …, i} que satisface ∑ wj ≤ W.
𝑗∈𝑆 𝑗∈𝑆
Habiendo definido esto, OPT(n,W) es lo que estamos buscando.

(6.8) Si w < wi entonces OPT(i,w) = OPT(i-1,w).

De lo contrario, OPT(i,w) = max(OPT(i-1,w), wi + OPT(i-1,w-wi)).

Algoritmo
Subset-Sum(n,W):
Matriz M[0 … n, 0 … W]
Inicializar M[0,w] = 0 para cada w = 0, 1, …, W
For i = 1, …, n
For w = 0, …, W
Usar (6.8) para computar M[i,w]
Endfor
Endfor
Return M[n,W]
(6.9) El algoritmo Subset-Sum computa correctamente el peso óptimo del problema, y es ejecutado en
O(nW).

➤ Llamamos a éstos algoritmos pseudo-polinómicos. Dichos algoritmos pueden ser eficientes cuando los
números involucrados {wi} son razonablemente pequeños. Por otro lado, éstos algoritmos pueden ser
menos prácticos a medida que éstos números crezcan.

➤ Para conseguir un conjunto óptimo S de solicitudes, podemos rastrearlas a través de la matriz M con un
procedimiento similar a los que hemos desarrollado anteriormente.

(6.10) Dada una matriz M de valores óptimos de los subproblemas, el conjunto óptimo S puede ser
encontrado en O(n).

Extensión: El Problema de la Mochila

Considere una situación en la cual cada solicitud i tiene un peso no negativo wi y tambien un valor distinto

vi. Nuestro objetivo ahora es encontrar un subconjunto S de valor máximo ∑ vi, sujeto a la restricción de
𝑖∈𝑆

que el peso total del conjunto no debe exceder W: ∑ wi ≤ W.

𝑖∈𝑆

(6.11) Si w < wi entonces OPT(i,w) = OPT(i-1,w).

De lo contrario, OPT(i,w) = max(OPT(i-1,w), vi + OPT(i-1,w-wi)).

(6.12) Éste problema es ejecutado en O(nW).

Segunda Estructura RNA - Programación Dinámica sobre Intervalos

Comenzaremos pensando sobre el conjunto de subproblemas sobre {1, …, j} para todo j, y se nos hará
imposible pensar en una recurrencia natural. Luego miraremos al conjunto más grande de subproblemas
en {i, i+1, …, j} para todo i y j (i ≤ j), y encontraremos una relación de recurrencia natural para estos
subproblemas. De ésta forma, hemos añadido una segunda variable i; el efecto es considerar un
subproblema para cada intervalo contíguo en {1, …, n}.

Una molécula RNA está formado por una sola hebra, formada por un string de bases {A, C, G, U}. El
conjunto de pares de bases (y su forma resultante) formado por la molécula RNA a través de su proceso
es llamado segunda estructura, y entender la segunda estructura es esencial para entender el
comportamiento de la molécula.

Para nuestros propósitos, la molécula RNA puede ser vista como una secuencia de n símbolos (bases) del
alfabeto {A, C, G ,U}. Sea B = b1b2…bn una molécula RNA, donde cada bi ∈ {A, C, G, U}. Para una primera
aproximación, uno puede modelar ésta estructura como sigue: Primero se requiere que A hace par con U,
y C hace par con G; tambien requerimos que cada base puede emparejarse como mucho con una otra
base (el conjunto de pares es un emparejamiento).
Concretamente, decimos que una segunda estructura en B es un conjunto de pares S = {(i,j)} donde i,j ∈
{1, …, n} que satisface las siguientes condiciones:
1. Los finales de cada par en S están separados mínimo por 4 bases entre medio; es decir que si (i,j) ∈ S
entonces i < j - 4.
2. Los elementos de cualquier par en S consisten en {A, U} o {C, G} (en cualquier orden).
3. S es un emparejamiento: ninguna base aparece en más de un par.
4. Si (i,j) y (k,l) son dos pares en S, entonces no se puede tener que i < k < j < l.

Ahora, para todas las segundas estructuras posibles para una única molécula RNA, cuáles son las que son
capaces de surgir sobre condiciones fisiológicas? La hipótesis usual es que una molécula RNA formará la
segunda estructura con el valor total óptimo de energía libre. El modelo correcto para la energía libre de
una segunda estructura asumiremos como una primera aproximación que será proporcional al número de
pares base que contenga.

Habiendo dicho esto, queremos un algoritmo eficiente que tome una molécula RNA B = b1b2…bn y
determine una segunda estructura S con el mayor número posible de pares base.

Un Primer Intento en la Programación Dinámica

Diremos que OPT(j) es el número máximo de pares base en una segunda estructura en b1b2…bj. Por la
condición 1 descrita más arriba, sabemos que OPT(j) = 0 para j ≤ 5; y sabemos que OPT(n) es la solución
que estamos buscando. El problema comienza cuando queremos escribir una recurrencia que exprese
OPT(j) en términos de las soluciones de problemas más pequeños: en la segunda estructura óptima
b1b2…bj, es el caso en el que sucede una de las 2 siguientes cosas:
● j no pertenece a ningún par, o
● j está emparejado con t, para algún t < j - 4
En el primer caso, solamente tenemos que consultar nuestra solución para OPT(j-1). El segundo caso,
debido a la condición 4 sabemos que ningún par puede tener un extremo entre 1 y t-1 y el otro entre t+1 y
j-1. Dado esto, hemos aislado 2 subproblemas nuevos: uno en las bases b1b2…bt-1, y otro en las bases
bt+1b2…bj-1. El primero se resuelve en OPT(t-1), pero el segundo no está en nuestra lista de subproblemas,
ya que no comienza con b1.

Dado esto, tenemos que añadir otra variable, ya que tenemos que ser capaces de trabajar con
subproblemas que no comienzan con b1; en otras palabras, necesitamos considerar subproblemas
bibi+1…bj para todas las opciones i ≤ j.

Programación Dinámica sobre Intervalos

Sea OPT(i,j) el número máximo de pares base en una segunda estructura en bibi+1…bj. La condición 1 nos
permite inicializar OPT(i,j) = 0 cuando i ≥ j - 4. Por conveniencia, también nos referiremos a OPT(i,j) = 0
cuando i > j.
Ahora, en la segunda estructura óptima bibi+1…bj, tenemos las mismas alternativas que teníamos antes:
● j no pertenece a ningún par, o
● j está emparejado con t, para algún t < j - 4
En el primer caso, tenemos OPT(i,j) = OPT(i,j-1). En el segundo caso, recurriremos a los 2 subproblemas
OPT(i,t-1) y OPT(t+1,j-1) como se argumentó anteriormente.

(6.13) OPT(i,j) = max(OPT(i,j-1), max(1 + OPT(i,t-1) + OPT(t+1,j-1))), donde el máximo es tomado sobre t
tal que bt y bj son un par base permitido (sobre las condiciones 1 y 2 de la definición de segunda
estructura).

La forma de (6.13) nos muestra que siempre estamos invocando la solución a subproblemas en intervalos
más cortos: aquellos en los cuales k = j - i es más pequeño. Debido a esto, funcionará sin ningún problema
si construimos las soluciones a medida que aumentamos el tamaño del intervalo.

Algoritmo
Inicializar OPT(i,j) = 0 siempre que i ≥ j - 4
For k = 5, …, n-1
For i = 1, …, n - k
Setear j = i + k
Computar OPT(i,j) usando (6.13)
Endfor
Endfor
Return OPT(1,n)

Se puede recuperar la segunda estructura en sí (no sólo su valor) almacenando como el mínimo en (6.13)
es alcanzado y luego recorrerlo.

➤ Hay O(n2) subproblemas para resolver, y evaluando la recurrencia en (6.13) toma un tiempo de
ejecución O(n) cada una; por lo que se concluye que el algoritmo se ejecuta en O(n3).

Alineación de Secuencias
Es un problema que surje al comparar strings. Siguiendo ésto, iremos al problema de computar los
caminos más cortos en un grafo cuando las aristas tiene un costo que podría ser negativo.

El problema surje, por ejemplo, si estamos buscando una definición de una palabra en un diccionario
online y escribimos algo que no se encuentra en el diccionario (por ejemplo ocurrance), nos preguntará “tal
vez quisiste decir occurrence?”; cómo sucede ésto?.
Para decidir lo que probablemente quisimos decir, sería natural buscar en dicho diccionario la palabra más
“similar” a la que escribimos.
Intuitivamente, nos gustaría decir que ocurrance y occurrence son similares porque podemos hacer que las
2 palabras sean idénticas si agregamos una c a la primer palabra, y cambiar la a por la e.

o- currance
occurrence

El guión indica un espacio en el cual tuvimos que agregar una letra a la segunda palabra para poder
alinearla con la primera. Igualmente, nuestro alineamiento no es perfecto ya que una e está alineada con
una a.
Queremos un modelo en el cual la similitud está determinada por el número de espacios (guiones) y
desajustes que surjan al alinear dos palabras.

Suponga que nos dan dos strings X e Y, donde X consiste en la secuencia de símbolos x1x2…xm e Y
consiste en la secuencia de símbolos y1y2…yn. Además, considere los conjuntos {1,...,m} y {1,...,n} que
representan las diferentes posiciones en los strings X e Y respectivamente; y considere un emparejamiento
de éstos conjuntos.

Alineación: Decimos que un emparejamiento M de éstos 2 conjuntos es una alineación si no hay pares
‘’cruzados’’: si (i,j), (i’,j’) ∈ M e i < i’, entonces j < j’.

stop-
-tops

Las anteriores palabras corresponden a la alineación {(2,1),(3,2),(4,3)}

Nuestra definición de similitud se basará en encontrar una alineación óptima entre X e Y, según el siguiente
criterio: Suponga que M es una alineación dada entre X e Y
● Primero, hay un parámetro δ > 0 que define el costo de un espacio. Para cada posición de X o Y que
no pertenezca a M (espacio -), sumamos δ.
● Segundo, para cada par de letras p, q en nuestro alfabeto, hay un costo ∝pq de mal-emparejado
(mismatch) por alinear p con q. Dado esto, por cada (i,j) ∈ M, pagamos el correspondiente ∝xiyk por
alinear xi con yk. Generalmente asumimos que ∝pp = 0 para cada letra p.
● El costo de M es la suma de los costos de sus espacios y sus malos-emparejamientos, y lo que
queremos es un alineamiento de costo mínimo.

(6.14) Sea M cualquier alineamiento de X e Y. Si (m,n) ∉ M, entonces alguna de las dos posiciones m ∈ X
o n ∈ Y no está emparejada en M.

(6.15) En una alineación óptima M, por lo menos una de las siguientes tres cosas son verdad:
1. (m,n) ∈ M; o
2. La posición m en X no está emparejada; o
3. La posición n en Y no está emparejada.

Denotaremos OPT(i,j) como el costo mínimo de un alineamiento entre x1x2…xi e y1y2…yj. Si se cumple el
caso 1 de (6.15), pagamos ∝xmyn y luego alineamos x1x2…xm-1 lo mejor posible con y1y2…yn-1; obtenemos
OPT(m,n) = ∝xmyn + OPT(m-1,n-1). Si se cumple el caso 2 de (6.15), pagamos el costo de un espacio δ ya
que la posición m de X no está emparejada, y luego alineamos x1x2…xm-1 lo mejor posible con y1y2…yn. En
éste caso, obtenemos OPT(m,n) = δ + OPT(m-1,n). Análogamente, si se cumple el caso 3 de (6.15)
obtenemos OPT(m,n) = δ + OPT(m,n-1).

(6.16) El costo mínimo de un alineamiento satisface la siguiente recurrencia para i ≥ 1 y j ≥ 1:

OPT(i,j) = min[∝xiyj + OPT(i-1,j-1), δ + OPT(i-1,j), δ + OPT(m,n-1)].
Además, (i,j) pertenece a un alineamiento óptimo M para éste subproblema si y sólo sí el mínimo es
alcanzado por el primero de éstos valores.

Solamente hay O(mn) subproblemas, y OPT(m,n) es el valor que estamos buscando.

Ahora especificaremos el algoritmo para computar el valor de la alineación óptima. Para inicializar,
denotaremos OPT(i,0) = OPT(0,i) = iδ para todo i, ya que la única forma de alinear una palabra de i letras
con otra palabra de 0 letras es usar i espacios.

Algoritmo
Alineacion(X,Y):
Matriz A[0…m, 0…n]
Inicializar A[i,0] = iδ para cada i
Inicializar A[0,j] = jδ para cada j
For j = 1, ..., n
For i = 1, …, m
Usar (6.16) para computar A[i,j]
Endfor
Endfor
Return A[m,n]

Podemos utilizar la segunda parte de (6.16) recorriendo la matriz A para construir el alineamiento en sí.

➤ El algoritmo es ejecutado en O(mn), ya que hay O(mn) entradas en la matriz y como mucho pasamos
un tiempo constante en cada entrada.

Éste problema tambien se puede resolver utilizando grafos dirigidos. Suponga que construímos una
cuadrícula mxn de un grafo GXY, con las filas etiquetadas con los símbolos del string X, las columnas
etiquetadas con los símbolos del string Y, y aristas dirigidas.
Numeramos las filas de 0 a m y las columnas de 0 a n; denotamos el nodo en la i-ésima fila y j-ésima
columna como (i,j). Ponemos costos en las aristas de GXY: el costo de cada arista horizontal y vertical es δ,
y el costo de la arista diagonal de (i-1,j-1) a (i,j) es ∝xiyj.

La recurrencia en (6.16) para OPT(i,j) es precisamente la recurrencia que uno obtiene para el camino de
costo mínimo en GXY desde (0,0) hasta (i,j).

(6.17) Sea f(i,j) el camino de costo mínimo desde (0,0) hasta (i,j) en GXY. Entonces para todo i y j tenemos
que f(i,j) = OPT(i,j).

A forma de ejemplo, en la siguiente figura se muestra el valor del camino más corto desde (0,0) hasta cada
nodo (i,j) para el problema de alinear las palabras mean y name. Para el propósito de éste ejemplo,
asumimos que δ = 2; emparejar una vocal con una vocal diferente o una constante con una constante
diferente cuesta 1; mientras que emparejar una vocal con una consonante cuesta 3. Para cada celda en la
cuadrícula (representando el nodo correspondiente), la flecha indica el último paso del camino más corto
dirigido a ese nodo, en otras palabras, la forma en la que el mínimo en (6.16) es alcanzado.

Caminos Más Cortos en un Grafo

Sea G = (V,E) un grafo dirigido. Asuma que cada arista (i,j) ∈ E tiene un costo asociado cij que puede ser
negativo.
Consideraremos los 2 siguientes problemas relacionados:
● Dado un grafo G con costos, decidir si G tiene un ciclo negativo; eso es, un ciclo dirigido C tal que

∑ cij < 0
𝑖𝑗 ∈ 𝐶
● Si el grafo no tiene ciclos negativos, encontrar un camino P comenzando en un nodo s hasta otro nodo t
con el mínimo costo tota:

∑ cij
𝑖𝑗 ∈ 𝑃

Tiene sentido considerar el problema del camino de mínimo costo sobre la suposición de queno hay ciclos
negativos. Si hay un ciclo negativo C, con un camino Ps desde s hacia el ciclo, y otro camino Pt desde el
ciclo hacia t podemos construir un camino s-t con costo negativo arbitrario: primero utilizamos Ps para
llegar al ciclo negativo C, luego damos vueltas en C la cantidad de veces que queramos, y luego utilizamos
Pt para ir de C al destino t.

Un acercamiento con Programación Dinámica

Trataremos de utilizar programación dinámica para resolver el problema de encontrar el camino más corto
de s a t cuando hay aristas con costo negativo pero no hay ciclos negativos. La solución que
desarrollaremos se basará en la siguiente observación:

(6.22) Si G tiene ciclos no negativos, entonces hay un camino de costo mínimo de s a t que es simple (no
repite nodos), por lo que a lo sumo tendrá n-1 aristas.

Usaremos OPT(i,v) para denotar el costo mínimo de un camino v-t usando a lo sumo i aristas. Por (6.22)
nuestro problema original es computar OPT(n-1,s). Ahora, simplemente necesitamos una manera sencilla
de expresar OPT(i,v) utilizando subproblemas más pequeños. Veremos que el acercamiento más natural
involucra la consideración de varias opciones diferentes.

Fijemos un camino óptimo P representando OPT(i,v):

● Si el camino P utiliza como mucho i-1 aristas, entonces OPT(i,v) = OPT(i-1,v).
● Si el camino P utiliza i aristas y la primer arista es (v,w), entonces OPT(i,v) = cvw + OPT(i-1,w).

(6.23) Si i > 0 entonces OPT(i,v) = min(OPT(i-1,v), minw∈V(OPT(i-1,w), cvw)).

Algoritmo
Camino-Más-Corto(G, s, t):
n = número de nodos en G
Matriz M[0…n-1, V]
Definir M[0,t] = 0 y M[0,v] = ∞ para todo otro nodo v ∈ V
For i = 1, …, n-1
For v ∈ V en cualquier orden
Computar M[i,v] utilizando (6.23)
Endfor
 Endfor
Return M[n-1,s]

(6.24) El método de Camino-Más-Corto computa correctamente el costo mínimo de un camino s-t en un

grafo que no tiene ciclos negativos, y su tiempo de ejecución es O(n3).

Dada la tabla M que contiene los valores óptimos de los subproblemas, el camino más corto usando como
mucho i aristas se puede obtener en O(in), recorriendo los subproblemas más pequeños.

A forma de ejemplo, considere el grafo en la figura (a), donde el objetivo es encontrar un camino más corto
desde cada nodo hasta t. La tabla en la figura (b) nos muestra la matriz M, donde cada entrada
corresponde al valor M[i,v] del algoritmo. Dado ésto, una única fila corresponde al camino más corto desde
un nodo particular hasta t, ya que permitimos que el camino use una cantidad de aristas que va
incrementando. Por ejemplo, el camino más corto desde el nodo d al nodo t se actualiza 4 veces, ya que
primero es d-t, segundo d-a-t, tercero d-a-b-e-t, y por último d-a-b-e-c-t.

Extensiones: Algunas Mejoras Básicas al Algoritmo

Un Análisis de Tiempo de Ejecución Mejorado: Un grafo dirigio con n nodos puede tener cerca de n2
aristas, ya que puede haber una arista entre cada par de nodos; pero muchos grafos tienen muchas menos
aristas que ésto. Cuando trabajamos con un grafo el cual el número de aristas m es significativamente
menor que n2, ya hemos visto que puede ser útil escribir el tiempo de ejecución en términos de m y n.

Si somos más cuidadosos en el análisis del método anterior, podemos mejorar el tiempo de ejecución a
O(mn) sin cambiar el algoritmo en sí.

(6.25) El método de Camino-Más-Corto puede ser implementado en O(mn).

Mejorando los Requerimientos de Memoria: En el algoritmo, la matriz es de tamaño n2, pero se puede
reducir a un arreglo de tamaño O(n). En vez de registrar M[i,v] para cada i, usaremos y actualizaremos un
único valor M[v] para cada nodo v, el largo del camino más corto de v a t que hayamos encontrado hasta el
momento. Seguiremos utilizando las iteraciones i = 1,...,n-1, pero el rol de i será únicamente como iterador;
en cada iteración y por cada nodo v, haremos la actualización M[v] = min(M[v], minw∈V(cvw + M[w])).
(6.26) A lo largo del algoritmo M[v] es el largo de algún camino de v a t, y luego de i actualizaciones, el
valor de M[v] no es más grande que el largo del camino más corto de v a t usando como mucho i aristas.

Encontrando los Caminos Más Cortos: Para ayudar a recuperar los caminos más cortos, mejoraremos
el código haciendo que cada nodo v mantenga el primer nodo (después de sí mismo) en su camino con
destino t; denotaremos ésto como first[v]. Para mantener first[v], actualizaremos su valor siempre que la
distancia M[v] sea actualizada. En otras palabras, cuando el valor de M[v] sea reseteado al mínimo
minw∈V(cvw + M[w]), setearemos first[v] con el nodo w que alcance ese mínimo.

Ahora, denotemos P como el ‘’grafo puntero dirigido’’, cuyos nodos son V y sus aristas son {v,first[v]}. La
principal observación es la siguiente:

(6.27) Si P contiene un ciclo C, entonces el ciclo tiene costo negativo.

Notemos que si G no tiene ciclos negativos, entonces (6.27) implica que P nunca va a tener un ciclo.

(6.28) Suponga que G no tiene ciclos negativos, y considere el grafo puntero P en la terminación del
algoritmo. Para cada nodo v, el camino de v a t en P es un camino v-t lo más corto posible en G.

Notemos que en la versión del algoritmo donde mejoramos los requerimientos de memoria, el camino cuyo
largo es M[v] luego de i iteraciones puede tener muchas más aristas que i. Debido a esto, necesitamos una
bandera en el algoritmo que nos diga que podemos terminar antes de la iteración n-1. Dicha observación
es una consecuencia simple de la siguiente observación: Si alguna vez ejecutamos una iteración completa
i en la cual ningun valor M[v] cambia, entonces ningun valor M[v] cambiará, ya que las iteraciones futuras
comenzaran con exactamente la misma cantidad de valores en las entradas en el arreglo. Dado esto,
podemos terminar el algoritmo tranquilamente. Note que no es suficiente para algun valor en particular
M[v], para terminar correctamente el algoritmo necesitamos que todos estos valores permanezcan iguales
para una única iteración.

Capítulo 7 - Red de Flujos

El Problema del Flujo Máximo

Usualmente se utilizan grafos para modelar redes de transportación; redes cuyas aristas llevan algún tipo
de tráfico y cuyos nodos actúan como ‘’interruptores’’ pasando el tráfico entre diferentes aristas. Considere
por ejemplo un sistema de carretera en el cual las aristas son las rutas y los nodos son intercambiadores.
Modelos de redes de éste tipo tienen varios ingredientes: capacidades en las aristas que indican cuánto
pueden llevar; nodos fuente que generan el tráfico, nodos destino que pueden ‘’absorber’’ el tráfico
mientras llega, y finalmente el tráfico mismo que es transmitido por las aristas.

Redes de Flujo: Consideraremos grafos de ésta forma, y nos referiremos al tráfico como flujo (una entidad
abstracta que es generada en nodos fuente, transmitida por las aristas, y absorbida en los nodos destino).
Formalmente diremos que una red de flujo es un grafo dirigido G = (V,E) con las siguientes
características:
● Cada arista e tiene asociada una capacidad, la cual es un número no negativo al cual denotaremos ce.
● Hay un único nodo fuente s ∈ V.
● Hay un único nodo destino t ∈ V.

Los demás nodos serán llamados nodos internos.

El nodo s no tiene ninguna arista entrante, así como el nodo t no tiene ninguna arista saliente. Además,
hay por lo menos una arista incidente a cada nodo y todas las capacidades son enteros.

Definiendo Flujo: Decimos que un flujo s-t es una función f que a cada arista e le asigna un número real
no negativo, f: E →R+; el valor f(e) intuitivamente representa la cantidad de flujo que una arista e lleva. Un
flujo f debe satisfacer las siguientes dos propiedades:
1. (Condición de Capacidad) Para cada e ∈ E, tenemos 0 ≤ f(e) ≤ ce.

2. (Condición de Conservación) Para cada nodo v distintos de s y t ∑ f(e) = ∑ f(e)

𝑒 𝑒𝑛𝑡𝑟𝑎𝑛𝑡𝑒 𝑎 𝑣 𝑒 𝑠𝑎𝑙𝑖𝑒𝑛𝑡𝑒 𝑑𝑒 𝑣

Aquí ∑ f(e) suma el valor f(e) del flujo entre todas las aristas que entran al nodo v, mientras que
𝑒 𝑒𝑛𝑡𝑟𝑎𝑛𝑡𝑒 𝑎 𝑣

∑ f(e) es la suma de los valores de flujo entre todas las aristas salientes del nodo v.
𝑒 𝑠𝑎𝑙𝑖𝑒𝑛𝑡𝑒 𝑑𝑒 𝑣

El valor de un flujo f, denotado v(f), se define como la cantidad de flujo generado en la fuente:

v(f) = ∑ f(e).
𝑒 𝑠𝑎𝑙𝑖𝑒𝑛𝑡𝑒 𝑑𝑒 𝑠

Para hacer la notación más compacta, definimos fout(v) = ∑ f(e) y fin(v) = ∑ f(e). Podemos
𝑒 𝑠𝑎𝑙𝑖𝑒𝑛𝑡𝑒 𝑑𝑒 𝑣 𝑒 𝑠𝑎𝑙𝑖𝑒𝑛𝑡𝑒 𝑑𝑒 𝑣

extender ésto a conjuntos de vértices; si S ⊆ Vdefinimos fout(S) = ∑ f(e) y fin(S) = ∑ f(e). En

𝑒 𝑠𝑎𝑙𝑖𝑒𝑛𝑡𝑒 𝑑𝑒 𝑆 𝑒 𝑠𝑎𝑙𝑖𝑒𝑛𝑡𝑒 𝑑𝑒 𝑆
ésta terminología, la condición de conservación para nodos v ≠ s, t se transforma en fout(v) = fin(v); además
podemos escribir v(f) = fout(s).

Dada una red de flujo, un objetivo natural es arreglar el tráfico de manera que hagamos lo más eficiente
posible el uso de la capacidad disponible. Dado ésto, consideraremos un algoritmo que resuelva que dada
una red de flujo encuentre un flujo del mayor valor posible.

Suponga que dividimos los nodos del grafo entre dos conjuntos A y B, de modo tal que s ∈ A y t ∈ B.
Entonces intuitivamente cualquier flujo que va de s a t debe cruzar de A a B en algún punto, por ende
utilizará alguna capacidad de una arista de A a B. Ésto sugiere que cada dicho ‘’corte’’ del grafo pone un
límite en el valor máximo que pueda tener el flujo. El algoritmo mayor-flujo que desarrollaremos aquí estará
relacionado con la prueba de que el mayor flujo es igual a la mínima capacidad de cualquier división,
llamada el corte mínimo.

Suponga que empezamos con cero flujo: f(e) = 0 para toda arista e. Claramente ésto cumple las
condiciones de capacidad y conservación; el problema es que su valor es 0. Ahora trataremos de
incrementar el valor de f impulsando flujo en algún camino s-t, respetando los límites impuestos por las
capacidades de las aristas.

Hay una forma más general de impulsar flujo: Podemos impulsar hacia adelante en las aristas que tienen
capacidad restante, y podemos impulsar hacia atras en las aristas que ya están llevando flujo para
desviarlo hacia otra dirección.

Grafo Residual: Dada una red de flujo G, y un flujo f en G, definimos el grafo residual de Gf con respecto a
f de la siguiente manera:
● El conjunto de nodos de Gf es el mismo que el de G.
● Para cada arista e = (u,v) de G en la cual f(e) < ce, hay ce - f(e) unidades restantes de capacidad en las
cuales podríamos tratar de impulsar flujo hacia adelante. Dado ésto, incluímos la arista e = (u,v) en Gf,
con una capacidad de ce - f(e). A las aristas incluídas de ésta forma las llamaremos aristas delanteras.
● Para cada arista e = (u,v) en G en la cual f(e) > 0, hay f(e) unidades de flujo que podemos ‘’deshacer’’ si
así lo queremos, impulsando flujo hacia atrás. Así que incluímos la arista e’ = (v,u) en Gf, con una
capacidad de f(e). Notar que e’ tiene los mismos nodos que e, pero su dirección es inversa; llamaremos
a éste tipo de aristas incluídas aristas traseras.

➤ Si 0 < f(e) < ce resulta que una arista delantera y una arista trasera serán incluídas en Gf. Dado ésto, Gf
tiene como mucho el doble de aristas que tiene G.

Aumentando Caminos en un Grafo Residual: Sea P un camino simple s-t en Gf. Definimos
bottleneck(P,f) como la mínima capacidad residual de cualquier arista en P, respecto al flujo f. Definimos la
siguiente operación aumentar(f,P), la cual nos indica que habrá un nuevo flujo f’ en G.

aumentar(f,P):
Sea b = bottleneck(f,P)
For each arista (u,v) ∈ P
If e = (u,v) es una arista delantera
Incrementar f(e) en G con b
Else ((u,v) es una arista trasera, y sea e=(v,u))
Decrementar f(e) en G con b
Endif
Endfor
Return f

➤ El resultado de aumentar(f,P) es un nuevo flujo f’ en G, obtenido al incrementar y decrementar los

valores de los flujos en las aristas de P.

(7.1) f’ es un flujo en G.
 Algoritmo Ford-Fulkerson
Max-Flow
Inicialmente f(e) = 0 para toda arista e en G
While haya un camino s-t en el grafo residual Gf
Sea P un camino simple s-t en Gf
f’ = aumentar(f,P)
Actualizar f con f’
Actualizar el grafo residual Gf con Gf ’
Endwhile
Return f

(7.2) En cualquier etapa intermedia del algoritmo Ford-Fulkerson, los valores del flujo {f(e)} y la capacidad
residual en Gf son enteros.

(7.3) Sea f un flujo en G, y sea P un camino simple s-t en Gf. Entonces v(f’) = v(f) + bottleneck(P,f); y como
bottleneck(P,f) > 0, tenemos que v(f’) > v(f).

Necesitamos una observación más para probar que el algoritmo termina: Necesitamos poder acotar el
máximo valor posible del flujo. Aquí tenemos un límite superior: Si todas las aristas salientes de s pudieran

ser completamente saturadas con el flujo, el valor del flujo sería ∑ ce. Denotemos ésta suma como
𝑒 𝑠𝑎𝑙𝑖𝑒𝑛𝑡𝑒 𝑑𝑒 𝑠
C. Tenemos que v(f) ≤ C para todos los flujos f en s-t.

(7.4) Suponga que todas las capacidades en la red de flujo G son enteros. Entonces, el algoritmo
Ford-Fulkerson termina en como mucho C iteraciones del while.

Hemos asumido que todos los nodos tienen por lo menos una arista incidente, por lo que m ≥ n/2 y
podremos utilizar O(m + n) = O(m)

(7.5) Suponga que todas las capacidades en la red de flujos G son enteros. Entonces, el algoritmo
Ford-Fulkerson puede ser implementado para ser ejecutado en O(mC).

➤ Una versión más eficiente del algoritmo mantendría la lista de aristas en el grafo residual Gf como parte
del procedimiento ‘aumentar’.

Flujos Máximos y Cortes Mínimos en una Red

Ya hemos visto una cota superior: el valor de v(f) de cualquier flujo s-t es como mucho ∑ ce.
𝑒 𝑠𝑎𝑙𝑖𝑒𝑛𝑡𝑒 𝑑𝑒 𝑠
Algunas veces ésta cota es útil, pero en otras ocasiones es bastante débil.
Considere dividir los nodos del grafo en dos conjuntos A y B, de tal manera que s ∈ A y t ∈ B. Como
hemos visto antes, cualquier división de esa forma impone una cota superior en el posible valor máximo de
flujo, ya que todo el flujo debe cruzar de A a B en algún punto.

Corte: Decimos que un corte s-t es una partición (A,B) del conjunto de vértices V, tal que s ∈ A y t ∈ B.
Capacidad de Corte: La capacidad de un corte (A,B), que denotaremos c(A,B), es simplemente la suma

de las capacidades de todas las aristas de salen de A: c(A,B) = ∑ ce.

𝑒 𝑠𝑎𝑙𝑖𝑒𝑛𝑡𝑒 𝑑𝑒 𝐴

(7.6) Sea f cualquier flujo s-t y (A,B) cualquier corte s-t. Entonces v(f) = fout(A) - fin(A).

➤ Esto nos dice que podemos medir el flujo exactamente: Es la cantidad total que se va de A, menos la
cantidad que vuelve hacia A.

(7.7) Sea f cualquier flujo s-t y (A,B) cualquier corte s-t. Entonces v(f) = fin(B) - fout(B).

(7.8) Sea f cualquier flujo s-t y (A,B) cualquier corte s-t. Entonces v(f) ≤ c(A,B).

➤ Esto nos dice que el valor de todo flujo está acotado superiormente por la capacidad de todo corte.

Sea f’ el flujo devuelto por el algoritmo Ford-Fulkerson. Queremos demostrar que f’ tiene el mayor valor
posible de cualquier flujo en G, y haremos esto según el método que discutimos anteriormente: Daremos
un corte s-t (A*,B*) para el cual v(f’) = c(A*,B*). Esto establece inmediatamente que f’ tiene el mayor valor
que cualquier flujo, y que (A*,B*) tiene la menor capacidad de cualquier corte s-t.

(7.9) Si f es un flujo s-t tal que no hay camino s-t en el grafo residual Gf, entonces hay un corte s-t (A*,B*)
en G para el cual v(f) = c(A*,B*). Como consecuencia, f tiene el mayor valor de cualquier flujo en G, y
(A*,B*) tiene la menor capacidad de cualquier corte s-t en G.

➤ El algoritmo Ford-Fulkerson termina cuando no hay s-t en el grafo residual, por lo que inmediatamente
(7.6) implica su optimalidad.

(7.10) El flujo f’ devuelto por el algoritmo Ford-Fulkerson es un flujo máximo.

(7.11) Dado un flujo f de máximo valor, podemos computar un corte s-t de mínima capacidad en O(m).

(7.12) En toda red de flujo, hay un flujo f y un corte (A,B) tal que v(f) = c(A,B).

El punto es que f en (7.12) debe ser un flujo máximo s-t; ya que si hubiera un flujo f’ de mayor valor, el
valor de f’ excedería la capacidad de (A,B), y esto contradice (7.8). De la misma forma, se obtiene que
(A,B) en (7.12) es un corte mínimo (ningún otro corte tiene menor capacidad), ya que si hubiera un corte
(A’,B’) de menor capacidad, sería menor que el valor de f, y esto nuevamente contradice (7.8).

(7.13) En toda red de flujo, el valor máximo de un flujo s-t es igual a la capacidad mínima de un corte s-t.

(7.14) Si todas las capacidades en la red de flujo son enteros, entonces hay un flujo máximo f para el cual
cada valor de flujo f(e) es un entero.
¿Qué pasa si tenemos números reales como capacidades? Nosotros utilizamos (7.2) para establecer en
(7.4) que el valor del flujo se incrementaba como mínimo en 1 en cada paso. Con números reales como
capacidades, nos debería preocupar que el valor de nuestro flujo se siga incrementando, pero en valores
que se van haciendo más pequeños, por lo que no podemos garantizar que el número de iteraciones del
loop es finito. Sin embargo, se puede probar que el teorema (7.12) es verdadero aún si las capacidades
son reales.

Eligiendo Buenos Caminos de Aumento

Anteriormente vimos que cualquier manera de elegir un camino de aumento incrementa el valor del flujo, y

esto nos lleva a una cota C sobre el número de aumentos, donde C = ∑ ce. Cuando C no es muy
𝑒 𝑠𝑎𝑙𝑖𝑒𝑛𝑡𝑒 𝑑𝑒 𝑠
grande, esto puede ser una cota razonable, sin embargo, es bastante débil cuando C es grande.

Recuerde que el aumento incrementa el valor del flujo máximo según la capacidad de bottleneck del
camino elegido; así que si elegimos caminos con capacidad de bottleneck bastante grande, estaríamos
haciendo un gran avance.

Una idea natural es elegir el camino que tiene la capacidad de bottleneck más grande. Teniendo que
encontrar tales caminos puede enlentecer cada iteración individual un poco. Evitaremos este
enletecimiento si no nos preocupamos de elegir el camino que tiene exactamente la capacidad de
bottleneck más grande. En su lugar, mantendremos un parámetro de escala Δ, y buscaremos caminos que
tienen una capacidad de bottleneck de por lo menos Δ.

Sea Gf(Δ) el subconjunto del grafo residual consistiendo únicamente en las aristas con capacidad residual
de por lo menos Δ. Trabajaremos con valores de Δ que son potencias de 2.

Algoritmo
Scaling Max-Flujo:
Inicialmente f(e) = 0 para toda arista e en G
Inicialmente setear Δ como la mayor potencia de 2 que no es más grande que la capacidad máxima
saliente de s: Δ ≤ maxe saliente de s ce
While Δ ≥ 1
While hay un camino s-t en el grafo Gf(Δ)
Sea P un camino simple s-t en Gf(Δ)
f’ = augment(f,P)
Actualizar f con f’ y actualizar Gf(Δ)
Endwhile
Δ = Δ/2
Endwhile
Return f
Primero observemos que el algoritmo anterior es una implementación del algoritmo Ford-Fulkerson. El
nuevo loop, el valor Δ, y el grafo restringido Gf(Δ) son usados únicamente para guiar la selección del
camino residual, con el objetivo de utilizar aristas con capacidad residual grande por el mayor tiempo
posible. Por lo tanto, todas las propiedades que probamos sobre el algoritmo original tambien son
verdaderas para esta nueva versión.

(7.15) Si las capacidades son valores enteros, entonces a lo largo del algoritmo Scaling Max-Flujo el flujo f
y las capacidades residuales se mantienen como valores enteros. Ésto implica que cuando Δ = 1, Gf(Δ) es
lo mismo que Gf, por ende cuando el algoritmo termina, el flujo f es del mayor valor posible.

(7.16) El número de iteraciones del primer while es como mucho 1 + log2 C (redondeado hacia arriba).

La parte más difícil es acotar el número de aumentos que se hacen en cada fase de scaling. La idea es
que estamos usando caminos que aumentan el flujo por mucho, por lo que debería haber pocos aumentos.
Durante la fase Δ-scaling, usamos únicamente aristas con capacidad residual de por lo menos Δ. Usando
(7.3) tenemos lo siguiente:

(7.17) Durante la fase Δ-scaling, cada aumento incrementa el valor del flujo con un valor de por lo menos
Δ.

(7.18) Sea f el flujo al final de la fase Δ-scaling. Hay un corte s-t (A,B) en G para el cual c(A,B) ≤ v(f) + mΔ,
donde m es el número de aristas en el grafo G. Como consecuencia, el flujo máximo en la red tiene un
valor de como mucho v(f) + mΔ.

(7.19) El número de aumentos en una fase scaling es como mucho 2m.

(7.20) El algoritmo Scaling Max-Flujo en un grafo con m aristas y capacidades de valor entero, encuentra
un flujo máximo en como mucho 2m(1 + log2 C (redondeado hacia arriba)) aumentos. Puede ser
implementado para que sea ejecutado en O(m2log2 C).

➤ Cuando C es grande, éste tiempo es mucho mejor que O(mC) que se obtenía a una implementación
arbitraria del algoritmo Ford-Fulkerson.

Capítulo 8 - NP Y Dificultad Computacional

Desde un punto de vista pragmático, NP significa “computacionalmente difícil para todos los propósitos
prácticos, pero no podemos probarlo”.

Reducciones de Tiempo Polinómico

Nuestro plan es explorar el espacio de problemas computacionalmente difíciles, llegando eventualmente a
una caracterización matemática de gran parte de ellos. Nuestra técnica básica en ésta exploración es
comparar la dificultad relativa de diferentes problemas; formalmente nos gustaría expresar declaraciones
como “Problema X es por lo menos tan difícil como problema Y”. Formalizaremos esto con la noción de
reducción: mostraremos que un problema particular X es por lo menos tan difícil como algún otro
problema Y diciendo que, si tuviéramos una ‘’caja negra’’ capaz de resolver X, entonces tambien
podríamos resolver Y. (En otras palabras, X es lo suficientemente poderoso como para permitirnos resolver
Y).

Para hacer esto preciso, añadiremos la suposición de que X puede ser resuelto directamente en tiempo
polinómico a nuestro modelo de computación. Suponga que tenemos una caja negra que podría resolver
instancias de un problema X, si escribimos el input para una instancia de X, entonces en un único paso, la
caja negra retornaría la respuesta correcta. Ahora podemos hacer la siguiente pregunta:

(*) ¿Se puede resolver instancias arbitrarias de un problema Y usando un número polinómico de pasos
computacionales estándares, más un número polinómico de llamadas a la caja negra que resuelve el
problema X?

Si la respuesta a ésta pregunta es sí, entonces escribimos Y ≤p X; leemos ésto como “Y es reducible en
tiempo polinómico a X”, o “X es por lo menos tan difícial como Y (con respecto al tiempo polinómico)”.

Una importante consecuencia de nuestra definición de ≤p es la siguiente. Suponga que Y ≤p X y que

realmente existe un algoritmo polinómico para resolver X. Entonces nuestra caja negra especializada para
X en realidad no es tan valiosa, la podemos reemplazar con un algoritmo que corra en tiempo polinómico
para X.

(8.1) Suponga Y ≤p X. Si X puede ser resuelto en tiempo polinómico, entonces Y puede ser resuelto en
tiempo polinómico.

La propiedad anterior resume una buena manera de diseñar algoritmos que corran en tiempo polinómico
para problemas nuevos: por reducción a un problema que ya sabemos como resolver en tiempo
polinómico.

(8.2) Suponga Y ≤p X. Si Y no puede ser resuelto en tiempo polinómico, entonces X no puede ser resuelto
en tiempo polinómico.

➤ Usaremos ≤p para establecer niveles relativos de dificultad entre problemas.

Una Primera Reducción: Conjunto Independiente y Cobertura de Vértices

Recuerde que en un grafo G = (V,E) decimos que un conjunto de nodos S ⊆ V es independiente si ningún
par de nodos en S están unidos por una arista.

En el capítulo 1, propusimos el problema de encontrar el conjunto independiente más grande en un grafo

G. Por propósitos de nuestra actual exploración en términos de reducibilidad, será mucho más conveniente
trabajar con problemas que tienen respuestas únicamente del tipo si/no, por lo que propondremos el
problema del Conjunto Independiente de la siguiente forma.

Dado un grafo G y un número k, existe en G un conjunto independiente cuyo tamaño sea al menos k?

De hecho, desde el punto de vista de la solución en tiempo polinómico, no hay una diferencia significante
entre la versión óptima del problema (encontrar el conjunto independiente más grande), y la versión
decisiva (decidir, si o no, si en G existe un conjunto independiente cuyo tamaño sea al menos un k dado).
Dado un método para resolver la versión óptima, automáticamente resolvemos la versión decisiva (para
cualquier k). Pero tambien hay una conversión menos obvia de esto: si podemos resolver la versión
decisiva de conjunto independiente para todo k, entonces tambien podemos encontrar un conjunto
independiente de tamaño máximo. Dado un grafo G de n nodos, simplemente resolvemos la versión
decisiva de conjunto independiente para cada k; el k más grande para el cual la respuesta es “sí” es el
tamaño del conjunto independiente más grande en G.

Ahora, para ilustrar nuestra estrategia básica para relacionar problemas difíciles entre ellos mismos, vamos
a considerar otro problema fundamental de grafos para el cual no hay ningun algoritmo eficiente conocido:
Cobertura de Vértices. Dado un grafo G = (V,E), decimos que un conjunto de nodos S ⊆ V es una
cobertura de vértices si cada arista e ∈ E tiene por lo menos uno de los extremos en S; lo que es difícil es
encontrar conjuntos pequeños. Formularemos el problema de Cobertura de Vértices de la siguiente forma:

Dado un grafo G y un número k, existe en G una cobertura de vértices cuyo tamaño sea como mucho k?

No sabemos como resolver Conjunto Independiente ni Cobertura de Vértices en tiempo polinómico, pero
qué podemos decir sobre su dificultad relativa? Ahora mostraremos que son equivalentemente difíciles,
estableciendo que Conjunto Independiente ≤p Cobertura de Vértices, y que tambien Cobertura de Vértices
≤p Conjunto Independiente.

(8.3) Sea G = (V,E) un grafo. Entonces S es un conjunto independiente si y sólo sí su complemento V - S

es una cobertura de vértices.

(8.4) Conjunto Independiente ≤p Cobertura de Vértices.

(8.5) Cobertura de Vértices ≤p Conjunto Independiente.

Para resumir, éste tipo de análisis ilustra nuestro plan en general: aunque no sabemos como resolver
ninguno de los dos problemas eficientemente, (8.4) y (8.5) nos dicen como podríamos resolver un
problema dada una solución eficiente del otro, y por lo tanto estos dos hechos establecen los niveles
relativos de dificultad de éstos problemas.

Reduciendo a un Caso Más General: Cobertura de Vértices a Cobertura de

Conjunto
Conjunto Independiente y Cobertura de Vértices representan dos géneros de problemas. Conjunto
Independiente puede ser visto como un problema de empaquetamiento: El objetivo es ‘’empacar’’ la mayor
cantidad de vértices posibles, sujeto a conflictos (las aristas) que tratan de evitar que uno haga esto. Por
otro lado, Cobertura de Vértices puede ser visto como un problema de cobertura: El objetivo es “cubrir“
escasamente todas las aristas en el grafo usando la menor cantidad de vértices posibles.

Cobertura de Vértices es un problema de cobertura descrito específicamente en el lenguaje de grafos; hay

un problema de cobertura más general, Cobertura de Conjunto, en el cual uno busca cubrir un conjunto
arbitrario de objetos usando una colección de conjuntos más pequeños. Podemos describir el problema de
Cobertura de Conjunto de la siguiente forma.
Dado un conjunto U de n elementos, una colección S1, …, Sm de subconjuntos de U, y un número k, existe
una colección de como mucho k de éstos subconjuntos la cual la unión es igual a U?

(8.6) Cobertura de Vértices ≤p Cobertura de Conjunto.

➤ Todas las reducciones que consideremos consistiran en establecer Y ≤p X transformando nuestra

instancia de Y a una única instancia de X, invocando nuestra caja negra para X en ésta instancia, y
reportando la respuesta de la caja como nuestra respuesta para la instancia de Y.

Tambien hay una generalización natural de Conjunto Independiente como un problema de

empaquetamiento para conjuntos arbitrarios. Específicamente, definimos el problema de
Empaquetamiento de Conjunto como sigue.

Dado un conjunto U de n elementos, una colección S1, …, Sm de subconjuntos de U, y un número k, existe

una colección de como mínimo k de éstos subconjuntos con la propiedad de que ninguno de ellos se
intersectan?

(8.7) Conjunto Independiente ≤p Conjunto de Empaquetamiento.

Reducciones via “Artefactos”: El Problema de Satisfacibilidad

Ahora introduciremos un conjunto de problemas un poco más abstractos, los cuales son formulados en
notación booleana. Como tal, modelan un amplio rango de problemas en los cuales necesitamos
establecer variables de decisión para satisfacer un conjunto dado de restricciones; dichos formalismos son
comunes, por ejemplo, en inteligencia artificial. Luego de introducir estos problemas, los relacionaremos
via reducción a los problemas basados en grafos y conjuntos que hemos considerado hasta ahora.

Los Problemas SAT y 3-SAT

Suponga que nos dan un conjunto X de n variables booleanas x1, …, xn; cada una puede tomar el valor de
0 o 1 (equivalentemente, “false” o “true”). Por un término sobre X, queremos decir una de sus variables 𝑥i
o su negación 𝑥i. Finalmente, una cláusula es simplemente una disyunción de distintos términos:
t1 ∨ t2 ∨ … ∨ tl
(De nuevo, cada ti ∈ {𝑥1, …, 𝑥n, 𝑥1, … 𝑥n}). Decimos que una cláusula tiene largo l si contiene l términos.

Una asignación de verdad para X es una asignación del valor 0 o 1 para cada 𝑥i; en otras palabras, es
una función v: X → {0,1}. La asignación v implícitamente le da a 𝑥i el valor opuesto de verdad de 𝑥i. Una
asignación satisface una cláusula C si hace que C sea evaluado en 1 sobre las reglas de la lógica
booleana; esto es equivalente a requerir que al menos uno de los términos en C reciba el valor 1. Una
asignación satisface una colección de cláusulas C1, …, Ck si hace que todos los Ci se evalúen en 1; en
otras palabras, si hace que la conjunción C1 ∧ … ∧ Ck se evalúe en 1. En éste caso, diremos que v es
una asignación satisfactoria con respecto a C1, …, Ck; y que el conjunto de cláusulas C1, …, Ck es
satisfactorio.
Ahora podemos describir el Problema de Satisfacibilidad, tambien referido como SAT:

Dado un conjunto de cláusulas C1, …, Ck sobre un conjunto de variables X = {𝑥1, …, 𝑥n}, existe una
asignación de verdad satisfactoria?

Hay un caso especial de SAT que será equivalentemente difícil pero es un poco más fácil de pensar; éste
es el caso en el cual todas las cláusulas contienen exactamente tres términos (correspondiendo a distintas
variables). Llamamos éste problema 3-Satisfacibilidad, o 3-SAT:

Dado un conjunto de cláusulas C1, …, Ck cada una de largo 3 sobre un conjunto de variables X = {𝑥1, …, 𝑥
n}, existe una asignación de verdad satisfactoria?

Tenemos que hacer n decisiones independientes (las asignaciones para cada 𝑥i) de manera tal de
satisfacer un conjunto de restricciones. Hay varias maneras de satisfacer cada restricciones por separado,
pero tenemos que arreglar nuestras decisiones para que todas las restricciones sean satisfacidas
simultáneamente.

Reduciendo 3-SAT a Conjunto Independiente

Para resolver una instancia de 3-SAT utilizando una caja negra para Conjunto Independiente, necesitamos
una manera de codificar todas estas restricciones booleanas en los nodos y aristas de un grafo, de modo
tal que satisfacibilidad corresponda a la existencia de un conjunto grande independiente.

(8.8) 3-SAT ≤p Conjunto Independiente.

➤ Imaginaremos una instancia de 3-SAT de la siguiente manera: Tenemos que elegir un término de cada
cláusula, y luego encontrar una asignación de verdad que haga que todos éstos términos se evalúen en 1,
por lo que satisfacerán todas las cláusulas. Por lo que se triunfa si se puede seleccionar un término de
cada cláusula de modo tal que ningun par de términos seleccionados tengan “conflicto”; decimos que dos
términos tienen conflicto si uno es igual a una variable 𝑥i y el otro es igual a su negación 𝑥i. Si evitamos
términos conflictivos, podemos encontrar una asignación de verdad que haga que los términos
seleccionados de cada cláusula se evalúen en 1.

➤ Primero, construimos un grafo G = (V,E) consistiendo en 3k nodos agrupados en k triángulos. Eso es,
para i = 1, …, k, construímos tres vértices vi1, vi2, vi3 unidos uno a los otros por aristas. A cada uno de éstos
vértices le damos una etiqueta; vij está etiquetado con el término j-ésimo de la cláusula Ci de la instancia de
3-SAT. Codificamos los conflictos añadiendo más aristas al grafo: Para cada par de vértices cuyas
etiquetas corresponden a términos que tienen conflicto, añadimos una arista entre ellos. Ahora hemos
destruído todos los conjuntos independientes de tamaño k o todavía existe alguno? No es claro, depende
si todavía podemos seleccionar un nodo de cada triángulo de manera tal que ningún par conflictivo de
vértices sea elegido. Pero ésto es precisamente lo que la instancia de 3-SAT requirió.

La instancia original de 3-SAT es satisfacible si y sólo sí el grafo G que hemos construído tiene un
conjunto independiente cuyo tamaño sea por lo menos k.

(8.9) Si Z ≤p Y, e Y ≤p X, entonces Z ≤p X.
➤ 3-SAT ≤p Conjunto Independiente ≤p Cobertura de Vértices ≤p Cobertura de Conjunto.

Certificación Eficiente y la Definición de NP

La reducibilidad entre otros problemas fue el primer principal ingrediente en nuestro estudio sobre
intratabilidad computacional. El segundo ingrediente es una caracterización de la clase de problemas con
los que estamos lidiando. Combinando estos dos ingredientes junto con un fuerte teorema de Cook y
Levin, produciremos algunas consecuencias sorprendentes.

El problema aquí es el contraste entre encontrar una solución y chequear una solución propuesta. Para
Conjunto Independiente o 3-SAT, no conocemos un algoritmo de tiempo polinómico para encontrar
soluciones, pero chequear una solución propuesta para éstos problemas puede ser realizado facilmente en
tiempo polinómico. Para ver que ésto no es problema totalmente trivial, considere el problema que
enfrentaríamos si tuviéramos que probar que una instancia de 3-SAT no fuese satisfasible. ¿Qué
“evidencia” podríamos mostrar (en tiempo polinómico) para convencer a alguien que la instancia es
insatisfacible?

Problemas y Algoritmos
La entrada a un problema computacional será codificada como un string binario s finito. Denotamos el
largo de s como |s|. Identificaremos un problema de decisión X con el conjunto de strings en los cuales las
respuesta es “sí”. Un algoritmo A para un problema de decisión recibe como entrada un string s y retorna el
valor “sí” o “no” (denotaremos el valor retornado como A(s)). Decimos que A resuelve el problema X si para
todos los strings s, tenemos A(s) = “sí” si y sólo sí s ∈ X.

Como siempre, decimos que A tiene un tiempo de ejecución polinómico si hay una función polinómica p(.)
tal que para toda entrada s, el algoritmo A termina en s en como mucho O(p(|s|)) pasos. A lo largo de libro,
nos hemos preocupado con problemas que pueden ser resueltos en tiempo polinómico.

P: Es el conjunto (el libro lo escribe en cursiva xd) de todos los problemas X para los cuales existe un
algoritmo A que resuelve X en tiempo de ejecución polinómico.

Certificación Eficiente
Ahora, ¿cómo podríamos formalizar la idea de que una solución a un problema puede ser chequeada
eficientemente, independientemente de si puede ser resuelto eficientemente?. Un “algoritmo de
comprobación” para un problema X tiene una estructura diferente a la de un algoritmo que busca resolver
el problema; para “chequear” una solución, necesitamos el string de entrada s, como tambien un string
“certificador” t que contenga la evidencia de que s es una instancia “sí” de X.

Certificador Eficiente: Decimos que B es un certificador eficiente para un problema X si se cumplen las
siguientes propiedades:
1. B es un algoritmo cuyo tiempo de ejecución es polinómico, y además toma dos argumentos s y t
como entrada.
 2. Hay una función polinomial p tal que para todo string s, tenemos s ∈ X si y sólo sí existe un string t
tal que |t| ≤ p(|s|) y B(s,t) = sí.

Un certificador eficiente B puede ser utilizado como la componente principal de un algoritmo de “fuerza
burta” para un problema X: Sobre una entrada s, probar todos los strings t de largo ≤ p(|s|) y ver si B(s,t) =
sí para cualquiera de éstos strings. Pero la existencia de B no nos provee ninguna forma clara para diseñar
un algoritmo eficiente que resuelva X; despues de todo, depende de nostros encontrar un string t que haga
que B(s,t) sea “sí”, y hay una cantidad exponencial de posibilidades para t.

NP: Una Clase de Problemas

NP: Definimos NP (el libro lo pone en cursiva) como el conjunto de todos los problemas para los cuales
existe un certificador eficiente.

(8.10) P ⊆ NP.

● Para el problema 3-SAT, el t certificado es una asignación de valores de verdad a las variables; el
certificador B evalúa el conjunto dado de cláusulas con respecto a su asignación.
● Para el problema de Conjunto Independiente, el t certificado es la identidad de un conjunto de por lo
menos k vértices; el certificador B comprueba que para éstos vértices ninguna arista una ningun par de
vértices.
● Para el problema Cobertura de Conjunto, el t certificado es una lista de k conjuntos de la colección
dada; el certificador B comprueba que la unión de éstos conjuntos sea igual al conjunto subyacente U.

(8.11) ¿Hay un problema en NP que no pertenece a P? ¿Se cumple que P = NP?

Que se cumpla que P = NP sería muy bueno para que fuese verdad. ¿Cómo podría haber una
transformación general desde la tarea de chequear una solución a la tarea mucho más difícil de
efectivamente encontrar una solución?

Problemas NP-Complete
En la ausencia de progreso en la pregunta de si se cumple que P = NP, la gente ha ido por una pregunta
relacionada pero más alcanzable: ¿Cuáles son los problemas más difíciles en NP? Las reducciones en
tiempo polinómico nos da una forma de direccionarnos a ésta pregunta y obtener una visión en la
estructura de NP.

Discutiblemente, la manera más natural de definir un problema “difícil” X es siguiendo las dos
propiedades: (i) X ∈ NP; y (ii) para todo Y ∈ NP, Y ≤p X. Llamaremos a X como un problema NP-complete.

(8.12) Suponga que X es un problema NP-complete. Entonces X puede ser resuelto en tiempo polinómco
si y sólo sí P = NP.

➤ Una consecuencia crucial de (8.12) es la siguiente: Si hay algún problema en NP que no pueda ser
resuelto en tiempo polinómico, entonces ningun problema NP-complete puede ser resuelto en tiempo
polinómico.
Satisfacibilidad de Circuito: Un Primer Problema NP-complete
Primero notemos que no es del todo obvio que los problemas NP-complete siquiera existen. ¿Por qué no
podrían existir dos problemas incomparables X’ y X’’ tal que no hay X ∈ NP con la propiedad de que X’ ≤p
X y X’’ ≤p X? ¿Por qué no podría existir una secuencia infinita de problemas X1, X2, … en NP, cada uno
estrictamente más difícil que el anterior? Para probar que un problema es NP-complete, uno debe mostrar
como podría codificar cualquier problema en NP.

Tal vez la elección más natural para un primer problema NP-complete es el problema de Satisfacibilidad de
Circuito.

Para especificar éste problema, necesitamos especificar precisamente a que nos referimos con circuito.
Considere los operadores booleanos estándar que usamos para definir el problema de Satisfacibilidad: ∧
(and), ∨ (or) y ㄱ (not). Nuestra definición de un circuito está diseñada para representar un circuito físico
construído a través de puertas que implementan éstos operadores. Así, definimos un circuito K como un
grafo dirigido acíclico etiquetado como el de la siguiente figura.

● Las fuentes (sources) en K (los nodos sin aristas entrantes) están etiquetados con una de las
constantes 0 o 1, o con el nombre de una variable distinta. Los nodos de éste tipo serán referidos
como las entradas (inputs) del circuito.
● Todo otro nodo está etiquetado con uno de los operadores booleanos ∧, ∨ o ㄱ; los nodos
etiquetados con ∧ o ∨ tendrán dos aristas entrantes, mientras que los nodos etiquetados con ㄱ
tendrán una arista entrante.
● Hay un único nodo sin aristas salientes, y representará la salida (output): el resultado que fue
computado por el circuito.

Un circuito computa una función de sus inputs en el siguiente sentido: Imaginemos las aristas como
“cables” que traen el valor 0/1 dependiendo del nodo que salgan. Cada nodo v distinto a los inputs tomará
los valores de su(s) arista(s) entrante(s) y aplicará el operador booleano que lo etiqueta. El resultado de
ésta ∧, ∨ o ㄱ operación será pasado por la(s) arista(s) saliente(s) de v. El valor final computado por el
circuito será el valor computado en el nodo output.

Ahora, el problema de satisfacibilidad de circuito es el siguiente. Nos dan un circuito como entrada, y
tenemos que decidir si hay una asignación de valores a las fuentes del circuito que causen que la salida
tome el valor 1. (Si ésto sucede, diremos que el circuito dado es satisfacible, y una asignación satisfactoria
es una que haga que el output sea 1).

(8.13) Satisfacibilidad de Circuito es NP-complete.

Como discutimos anteriormente, la prueba de (8.13) requiere que consideremos un problema arbitrario X
en NP, y probemos que X ≤p Satisfacibilidad de Circuito. Usamos el hecho de que cualquier algoritmo que
tome un número n fijo de bits como entrada y produzca una respuesta sí/no, puede ser representado por
un circuito del tipo que acabamos de definir: El circuito es equivalente al algoritmo en el sentido que su
salida es 1 precisamente en las salidas para las cuales el algoritmo produzca una respuesta del tipo sí.
Más aún, si el algoritmo toma un número de pasos que es polinomial con respecto a n, entonces el circuito
tiene un tamaño polinomial.

¿Cómo podríamos utilizar ésta relación entre algoritmos y circuitos? Estamos intentando de probar que X
≤p Satisfacibilidad de Circuito (eso es, dada una entrada s, queremos decidir si s ∈ X usando una caja
negra que pueda resolver instancias de Satisfacibilidad de Circuito). Ahora, todo lo que sabemos sobre X
es que tiene un certificador eficiente B(.,.). Entonces, para determinar si s ∈ X, para alguna entrada
específica s de largo n, necesitamos responder la siguiente pregunta: ¿Hay algún t de largo p(n) que
cumpla que B(s,t) = sí?.

Como lo único que nos preocupa es la respuesta a una entrada específica s, visualizamos B(.,.) como un
algoritmo sobre n + p(n) bits (la entrada s y el certificado t), y lo convertimos a un circuito K de tamaño
polinómico con n + p(n) fuentes. Las primeras n fuentes serán codificadas con los valores de los bits en s,
y las p(n) fuentes restantes serán etiquetadas con las variables representando los bits de t; éstas últimas
fuentes serán las entradas para K.

Ahora simplemente observamos que s ∈ X si y sólo sí hay una forma de configurar la entrada de bits a K
de forma tal que el circuito produzca una salida con valor 1.

Un Ejemplo
Dado un grafo G, contiene un conjunto independiente de 2 nodos?

Veamos como una instancia de éste problema puede ser resuelta construyendo una instancia equivalente
de Satisfacibilidad de Circuito.

Primero tenemos que considerad un certificador eficiente para éste problema. La entrada s es un grafo con
n nodos, que será especificado por (n2) bits: Para cada par de nodos, habrá un bit representando si hay una
arista uniendo ese par. El certificado t puede ser especificado por n bits: Para cada nodo, habrá un bit
diciendo si éste nodo pertenece al conjunto independiente propuesto. El certificador eficiente ahora
necesita chequear dos cosas: que por lo menos 2 de los bits en t tienen valor 1, y que ningun par de bits
en t tienen valor 1 si éstos tienen una arista en común (según lo determinado en el correspondiente bit en
s).

Ahora construímos un circuito equivalente K. Suponga por ejemplo que estamos interesados en decidir la
respuesta a éste problema para un grafo G sobre los 3 nodos u, v y w; los cuales v está unido con u y w.
Ésto significa que tenemos una entrada de largo n = 3. La figura de abajo muestra un circuito que es
equivalente a un certificador eficiente para nuestro problema en un grafo arbitrario de 3 nodos.
Esencialmente, la parte derecha del circuito comprueba que al menos dos nodos han sido seleccionados, y
la parte izquierda comprueba que no hemos seleccionado un par d nodos que comparten una arista.
Codificamos las aristas de G como constantes en las primeras 3 fuentes, y dejamos las 3 restantes fuentes
(representando la elección de nodos a poner en el conjunto independiente) como variables. Ahora
observemos que ésta instancia de satisfacibilidad de circuito es satisfacible para la asignación 1, 0, 1 a las
entradas. Ésto corresponde a elegir los nodos u y w, los cuales efectivamente formas un conjunto
independiente de dos nodos sobre el grafo G.

Probando Más Problemas NP-Complete

(8.14) Si Y es un problema NP-complete, y X es un problema en NP con la propiedad de que Y ≤p X,
entonces X es NP-complete.

(8.15) 3-SAT es NP-complete.

Usando (8.14), (8.15) y la secuencia de reducciones 3-SAT ≤p Conjunto Independiente ≤p Cobertura de

Vértices ≤p Cobertura de Conjunto, se concluye lo siguiente:

(8.16) Todos los siguientes problemas son NP-complete: Conjunto Independiente, Conjunto de
Empaquetamiento, Cobertura de Vértices y Cobertura de Conjunto.

Estrategia General Para Probar Problemas Nuevos NP-Complete

Dado un nuevo problema X, daremos una estrategia básica para probar que es NP-complete
1. Probar que X ∈ NP.
2. Elegir un problema Y que sabemos que es NP-complete.
3. Probar que Y ≤p X. Considere una instancia arbitraria sY del problema Y, muestre como contruir (en
tiempo polinómico) una instancia sX del problema X que satisface las siguientes propiedades:
● Si sY es una instancia “sí” de Y, entonces sX es una instancia “sí” de X.
● Si sX es una instancia “sí” de X, entonces sY es una instancia “sí” de Y.
En otras palabras, ésto establece que sY y sX tienen la misma respuesta