Segundo Parcial 11/07/2003 (Algoritmos III)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia


1)

[B]__2__[I]_11___[A]__3__[E]_11___[G]__5__
   \_2__[D]__7__/   \_3__[H]__7__/        \
                                           [fin]
[F]_13____________________________[C]_13__/


El tiempo minimo sera:
max[13+13, max[2+11,2+7] + max[3+11,3+7] + 5] = max[26, 13 + 14 + 5] = max[26,32] = 32


2)
a) Si G es arbitrariamente atravesable desde un vertice (sea v0) -> Todo ciclo simple contiene a v0, entonces las particiones siempre tienen la misma cant. de ciclos
b) La trifuerza (para los que no conocen a Zelda:)

    o
   / \
  o---o
 / \ / \
o---o---o


Se puede ver que o se puede tomar los 3 triangulos de afuera (teniendo una part. de 3 circuitos), o bien el triangulo de arriba y el del medio (teniendo una de 2 circuitos)


3) m = i=1 a X'(G) |Mi| <= i=1 a X'(G)max{|Mi|} = X'(G)*|Mmax|


4)
Si f es un flujo valido:

  • 0 <= f(e) <= c(e)

f1 y f2 son validos -> 0 <= f1 <= c(e) y 0 <= f2 <=c(e)
-> 0 <= α*f1 <= α*c(e) y 0 <= (1-α)*f2 <= (1-α)*c(e)
-> 0 <= α*f1+(1-α)*f2 <= α*c(e)+(1-α)*c(e) = c(e) -> 0 <= f(e) <= c(e)

  • Σ{e en In(v)} f(e) = Σ{e en Out(v)} f(e) (salvo s y t)

f1 y f2 son validos -> Σ{e en In(v)} f1(e) = Σ{e en Out(v)} f1(e) y Σ{e en In(v)} f2(e) = Σ{e en Out(v)} f2(e)
[1.1] α*Σ{e en In(v)} f1(e) = [1.2] α*Σ{e en Out(v)} f1(e)
[2.1] (1-α)*Σ{e en In(v)} f2(e) = [2.2] (1-α)*Σ{e en Out(v)} f2(e)
[1.1]+[2.1] = α*Σ{e en In(v)} f1(e) + (1-α)*Σ{e en In(v)} f2(e) = Σ{e en In(v)} [ α*f1(e) + (1-α)*f2(e) ] = Σ{e en In(v)} f(e)
[1.2]+[2.2] = α*Σ{e en Out(v)} f1(e) + (1-α)*Σ{e en Out(v)} f2(e) = Σ{e en Out(v)} [ α*f1(e) + (1-α)*f2(e) ] = Σ{e en Out(v)} f(e)
-> Finalmente, sumando las dos igualdades anteriores -> Σ{e en In(v)} f(e) = Σ{e en Out(v)} f(e)


5)
a)Transformo en A=A, k=2, b=n/2, n=Σ{a en A} a. Para resolver П1, pregunto si A puede particionarse en 2 conjuntos tq Σ{a en A} a <= n/2
=>)П1 dice SI con A -> Existe A' A tq suma(A-A')=suma(A)
Como Σ{a en A} a = n -> Σ{a en A} a + Σ{a en A'} a = n -> Σ{a en A'} a = n/2, Σ{a en A-A'} a = n/2 -> (A', A-A') es una part. de A en 2 conj. tq suman <= n/2
<=)П2 dice SI con A -> A' se puede particionar en 2 conj. A', A-A' tq Σ{a en A'} a = n/2 y Σ{a en A-A'} a = n/2. Como Σ{a en A} a = n -> Σ{a en A'} a = n/2 y Σ{a en A-A'} a = n/2
b) Dado que en el item anterior encontramos una reduccion polinomial de П1 a П2 y П1 es NP-Completo => por definicion de NP-Completo para todo problema П que pertenece a NP es reducible polinomialmente a П1 y como П1 es reducible polinomialmente a П2, por transitividad todo problema П que pertenece a NP es reducible polinomialmente a П2, y como no sabemos si П2 pertenece a NP(no pide que lo veamos) lo unico que podemos asegurar es que П2 pertenece a NP-Hard
c)