Segundo Parcial 04/08/2003 (Algoritmos III)

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


1) (Revisar este) Sup. que no. Sea M un matching maximo, y u-w un eje en M. Luego v conecta con otro vertice que esta "saturado" en M (v no esta aislado). Pero entonces se tiene u-w-v, podria reemplazar el eje de M por w-v, con lo cual v esta en un matching maximo -> ABS


2)
a)
b) y c) Sup. este K4:

  1
 o--o--\
1|\0|2 |
 | \|  |100
 o--o  |
 | 1   |
 \-----/


Como se puede ver, hay un unico circ. hamiltoniano de peso minimo (1-1-1-2), pero el camino hamiltoniano de peso minimo es 1-0-1 -> F


3)
Creo que es muy parecido al 1) de 06/dic/2005


4)
Se puede hacer lo siguiente:
CLIQUEMAX(G,k) dice SI <=> SCM(G,Kk, k(k-1)/2) dice SI


5)
a)Sup. Existe H sub. ind. de G tq no es perfecto. Entonces existe H' ind. de H tq X(H)!=W(H). pero H' tambien es ind. de G -> G no era perfecto -> ABS
b)