TEORIA DE LA COMPUTACIÓNCAPÍTULO 1

PROBLEMAS Y ALGORITMOS

Gráfico de Accesibilidad Flujo máximo Coincidencia Problema del vendedor Viajante

Gráfico de Accesibilidad

Problema 1 Dado un grafo dirigido G = (V, E), donde V = {1, 2, . . . , n}, Cual es el camino desde el nodo 1 al nodo n.

1

2 3

4

5

1 → 4 → 3 → 5

1

2 3

4

5

ALgoritmo

1. Sea S = {1}.2. Si S está vacía, vaya a 5; de lo contrario, eliminar un nodo, decir t,

en S.3. Para cada borde (t, u) ∈ E, si u no está marcada, marque u y

añadir u a S.4. Ir a 2.5. Si el nodo n se marca, la respuesta "sí"; de lo contrario responder

"no".

Problema 1.4.2

Mostrar por inducción sobre i que si v es el nodo i-ésimo añadido por el algoritmo de búsqueda para el conjunto S, entonces hay un camino desde el nodo 1 a v.

Mostrar por inducción en l que si el nodo v es accesible desde el nodo 1 a través de un camino con L bordes, entonces el algoritmo de búsqueda añadirá v para establecer S.

EJEMPLO

1

2 3

4

5

S t

1

3

4

5

{ 1}

{ 3, 4}

{ 5, 4}

{ 5}

{ }

COMPLEJIDAD

1. Observe que cada nodo puede permanecer en S como máximo una vez.

2. Cada borde se utiliza como máximo una vez.3. Hay en la mayoría de los bordes de N^2.4. La complejidad de tiempo es en la mayoría de n^2.5. complejidad espacial es n.

OBSERVACIÓN

1. ¿Cómo implementar el Paso 2 en el algoritmo?Pila => DFS, cola => BFS

2. Cómo implementar Paso 3? Memoria de acceso aleatorio.3. ¿Cuál es el modelo computacional?4. Big-O.

Algoritmo de tiempo Polinómico

tiempo polinomial ⇒ práctico, eficiente tiempo exponencial ⇒ impráctico, ineficiente (intratable) Algoritmo n80 v.s. Algoritmo 2n/100

Peor Caso V.S. caso promedio El rendimiento de un algoritmo exponencial en el peor caso se

debe a una fracción insignificante estadística en laentrada.

Flujo máximo

Una red N = (V, E, s, t, c) es un gráfico (V, E) con dos nodos s especificados (la fuente) y T (el pozo) tal que la fuente no tiene bordes entrantes y el pozo no tiene bordes salientes;

para cada arista (i, j), se nos da una capacidad de c (i, j), un entero positivo.

Una Red

t

3

s

2

2

4

3

Flujo

1. una asignación de un valor entero no negativo f (i, j) ≤ c (i, j) para cada arista (i, j);

2. para cada nodo, aparte de s y t, la suma de los fs de los bordes entrantes es igual a la suma de los bordes salientes; ()

3. el valor de un flujo es la suma de los flujos en los bordes dejando s(o, equivalentemente, la suma de venir a T).

Máximo Problema de Flujo

Dada una red, encontrar un flujo del mayor valor posible.

s t

2/1

3/3

1/1

2/2

1/1

4/3

3/1

Algoritmo

s t

2/1

3/0

1/1

2/0

1/0

1/1

4/1

3/0

s t

2/1

3/1

1/1

2/0

1/1

4/1

3/1

s t s

2/1

3/3

2/2

1/1

4/3

3/1

t

1

3

1

2

1

1

1

2

Otro Ejemplo

Requerir un tiempo de O(n3C) en el peor de los casos!

s

C

C

1

C

C

Mejoras

La heurística de la ruta más corta puede reducir el tiempo para O(n5)

Coincidencia Bipartita

Un grafo bipartito es un triple B = (U, V, E) donde U = {u1,. . . , Un}, V = {v1,. . . , Vn}, y E ⊆ U × V.