Primer Parcial 18/05/2002 (Algoritmos III)

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


1)
2)
a)
b)
c)V Sup. que Emin tiene un ciclo. Sean v,w dos vertices del ciclo. Entonces tienen 2 formas de llegar uno al otro. Con lo cual v es inc. a 2 ejes: ev (el del peso minimo que conecta v) y el eje vw. Entonces ese eje debe ser el de peso minimo de w, pero w tambien es incidente al eje que proviene del otro camino. Pero entonces al ser todos ejes distintos, en Emin w es incidente a un eje que no es minimo -> ABS (Por def. de Emin)
d)e)f) F Sea G este grafo:

a     b       c     d
o_(1)_o_(100)_o_(1)_o


Entonces, en este caso Emin = {ab, cd}. Con lo cual al faltarle el eje de peso 100 no es conexo, con lo cual no es arbol (por lo tanto no es ni AG ni AGM)
g)Esto es igual al a)
h)Esto es igual al b)


3)
Exactamente igual al Ej. 2 del Parcial 20/may/2006


4)

PROCEDURE SubSecMaxima(VAR X,Y:SECUENCIA;n,m:CARDINAL;VAR L:TABLA);
VAR i,j:CARDINAL;
BEGIN
	FOR i:=0 TO m DO (* condiciones iniciales *)
		L[i,0].numero:=0
	END;
	FOR j:=0 TO n DO
		L[0,j].numero:=0
	END;
	
	FOR i:=1 TO m DO
		FOR j:=1 TO n DO
			IF Y[i] = X[j] THEN
				L[i,j].numero:=L[i-1,j-1].numero+1;
				L[i,j].procedencia:="D"
			ELSIF L[i-1,j].numero >=L[i,j-1].numero THEN
				L[i,j].numero:=L[i-1,j].numero;
				L[i,j].procedencia:="S"
			ELSE
				L[i,j].numero:=L[i,j-1].numero;
				L[i,j].procedencia:="I"
			END
		END
	END
END

Para reconstruir la secuencia se puede utilizar:

PROCEDURE Escribir(VAR L:TABLA; VAR Y:SECUENCIA; i,j:CARDINAL;
VAR sol:SECUENCIA; VAR l:CARDINAL);
(* sol es la secuencia solucion, l su longitud, i es la longitud
de la secuencia Y, y j la de X *)
BEGIN
	IF (i=0) OR (j=0) THEN RETURN END;
	IF L[i,j].procedencia = "D" THEN
		Escribir(L,Y,i-1,j-1,sol,l);
		sol[l]:=Y[i];
		INC(l);
	ELSIF L[i,j].procedencia = "S" THEN
		Escribir(L,Y,i-1,j,sol,l)
	ELSE
		Escribir(L,Y,i,j-1,sol,l)
	END
END


5)
a) En un triangulo orientado todos los vertices tienen grado 2, y din=dout=1. como G es conexo, entonces siempre debe haber un vertice en comun entre dos triangulos orientados, con lo cual a los grados de entrada y de salida de cada vertice se agregarian los ejes de entrada y salida de los otros triangulos, con lo cual siempre queda din=dout=1 para todo vertice. Entonces G contiene un circuito euleriano orientado -> es fuertemente conexo.
b) K4 (no se puede orientar en forma triangular), y como todo vertice tiene grado impar -> no tiene circ. euleriano -> no es fuertemente conexo.