Segundo Parcial 09/08/2004 (Algoritmos III)

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


1) Sea G un grafo no necesariamente conexo formado por 2k vertices de grado impar, donde (el grafo no contiene otros vertices). Demostrar que los ejes de G pueden particionarse en k caminos sin ejes repetidos.
(Revisar este)

Si se agregan k ejes, se puede lograr que todos los vertices tengan grado par, por lo tanto el grafo contiene un circuito euleriano. Entonces ahora es posible extraer k ejes, de tal manera que se obtienen k caminos diferentes


otra forma

la forma de ariba me parece q pincha si el grafo es completo o si tiene vertices de grado n - 1, es decir grado màximo

Agrego un vertice llamado w a G y lo uno con todos los vertices de G y formo un grafo q llamo G'

Ahora bien , en G' vale q tdo vertice tiene grado par, pues d(v') = d(v) + 1 ecepto por w q tiene grado 2k, pues es adyacente a todos los nodos q estaban en G

Entc existe C , ciclo Euleriano en G' que contien a los 2k ejes nuevos y que el mismo pasa por w , k veces ( pues entra y sale k veces , por q tiene grado 2k).

    w1---o---o---w2--- ...   wi    bueno algo asi.si sacamos los o---wi---o
    |                        |     del ciclo nos quedan solo los ejes de G
    wk---o      ...    o--o--o     y tambien nos quedan k pedazos del ciclo
                                   euleriano.

Se q no puede ocurrir lo siguiente:

   wi---v---wj 

pues solo existe un eje q une a v con w, segun como fue construido G' asi q los caminos tiene al menos un eje q lo compone.



2) Sea G = (n 3) un grafo completo no dirigido con pesos arbitrarios asociados a sus ejes. Sea (G) cualquier eje de G que tenga peso minimo y (G) cualquier eje de G que tenga peso maximo, ¿Es cierto que...
(a) (G) pertenece a algun camino hamiltoniano de peso minimo de G?
(b) (G) pertenece a todo camino hamiltoniano de peso minimo de G?
(c) (G) no pertenece a algun camino hamiltoniano de peso minimo de G?
(d) (G) no pertenece a ningun camino hamiltoniano de peso minimo de G?
Repetir suponiendo que los pesos cumplen la desigualdad triangular. En todos los casos justificar la respuesta


Con 4 contraejemplos sale (si los hice bien jeje)
a) F Sup. que tenemos este caso de un K4:

  2
 o--o--\
3|\1|4 |
 | \|  |100
 o--o  |
 | 5   |
 \-----/


Si se fijan, el circ. hamiltoniano de peso minimo es recorrer el cuadrado de forma 2-4-5-3, es decir, si se pasa por el eje de peso minimo (1) no queda otra que pasar por el eje de afuera (100), con lo cual no puede ser el minimo
b) F Idem a)
c) F Sup. que tenemos un K3. entonces hay un unico circ. hamiltoniano, por lo tanto es el de peso minimo (Claramente el eje maximo va a estar siempre)
d) F Idem c)
Mmm desigualdad triangular.. se los debo :P


3) (a) Presentar un grafo no planar que tenga la menor cantidad posible de nodos. Justificar.
(b) Presentar un grafo no planar que tenga la menor cantidad posible de ejes. Justificar.

a) b)


4) Dada la siguiente red donde cada arco tiene un flujo y una capacidad asignados, encontrar el camino de aumento que produce el mayor aumento posible en el flujo. Justificar.

Los caminos de aumento son:
s->(3,7)->(3,5)->(4,5)->(4,6)->t
s->(3,7)->(3,5)<-(6,6)<-(2,2)->(0,8)->(4,6)->t
El primer camino permite aumentar 1 y el segundo 2


5) Sean y los siguientes problemas.
: PARTICION
Entrada: un conjunto A de enteros positivos.
Pregunta: ¿existe A' A tal que suma(A') = suma(A-A')?
: KRR
Entrada: un conjunto B de rectangulos en el plano y un contenedor C que tambien es un rectangulo en el plano. Todos estos rectangulos tienen lados paralelos a los ejes del sistema de coodenadas.
Pregunta: ¿es posible desplazar en el plano los rectangulos de B (sin rotarlos), de tal manera que queden ubicados dentro de C sin que se superpongan entre si(salvo sus bordes)?
(a) Encontrar una reduccion polinomial de a . Demostrar que efectivamente es una reduccion polinomial.
(b) ¿Que se puede decir de sabiendo que es NP-Completo? Justificar.


Este era MUY parecido al 5) de 11/jul/2003