Primer Parcial 22/05/2004 (Algoritmos III)

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


1)
a)V Si G es bipartito -> Existen dos particiones V1,V2 de G tq todos los ejes tienen un extremo en V1 y otro en V2. Esto significa que cualquier subgrafo sera equivalente a tomar vertices de las dos particiones, que tambien podran distribuirse para formar un grafo bipartito
b)V (parecido al a)
c)V Si todos los subgrafos de G son bipartitos -> G tambien (es subgrafo de si mismo)
d)F Si se toma K3, este no es bipartito pero todos sus subgrafos propios lo son


2)
Este ej. se puede modelar tomando como vertices el conj. de quienes cruzaron el rio, poner ejes cuando dos situaciones puedan ocurrir una despues de la otra y asignando 1 a todos los pesos. Se puede resolver eficientemente con BFS


3)
Creo que sale por induccion


4)

Nota: costo=int, pred: <int,int>
camMinimo(int M[m][n])
	Tupla<costo, pred> R[m][n];
	Lista<int> camino;

	R(1,1)=< M[1,1], <0,0> >;
	R(f,1)=< Σ{i=1..f} M[i,1], <f-1,1> >;
	R(1,c)=< Σ{i=1..c} M[1,i], <1,c-1> >;

	para f=2..m
		para c=2..n
			si (R[f,c-1].costo < R[c-1,f].costo)
				R[f,c].costo = R[f,c-1].costo+M[f,c];
				R[f,c].pred = <f,c-1>;
			sino
				R[f,c].costo = R[f-1,c].costo+M[f,c];
				R[f,c].pred = <f-1,c>;

	res = R[m,n].costo;				
	
	sig = <m,n>;
	mientras (sig.pred != <0,0>) // reconstruyo camino
		camino = sig.pred U camino;
		sig = sig.pred;


La complejidad es O(m*n) y la matriz quedaria:

2	10	13	17
7	10	14	19
8	10	12	13
11	14	18	18