Segundo Parcial 15/07/2005 (Algoritmos III)

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


1)
a)
Primero pasa por s->(3,4)<-(3,4)<-(1,2)->(2,3)->t. Como el minimo de los "delta" es 1, el camino queda asi: s->(4,4)<-(2,4)<-(0,2)->(3,3)->t. Ahora no hay mas caminos de aumento, asi que cortando los ejes que van a T el flujo queda: F=7+2+3=12
b) En este caso cortar los ejes que van a T


2)
Como todos los vertices son de grado par -> todas las comp. conexas tienen circuito euleriano. Entonces un digrafo tiene circuito euleriano orientado <=> din(v) = dout(v)


3)
a) Todo grafo bipartito de 9 vertices o mas tendra en una de sus particiones 5 vertices o mas, con lo cual es imposible evitar el K5 en el complemento -> el complemento nunca sera planar
b)
http://serv2.imagehigh.com/imgss/4548401_bip8vnp.JPG


4)
Hagamos una "tablita":
n | 1 2 3 4 5 ..
V | 2 4 6 8 10 ..
E | 1 4 9 16 25 ..
Entonces los 1eros son:

o-o   o-o
      |/
      o-o


Y los demas se pueden hacer agregando siempre un o-o, tal que uno de los vertices este conectado a todos los del grafo anterior, y siempre queda un grafo con un unico matching perfecto(Prueben Prueben!!)


5)
Me parece que hay que mandar una matriz tq M[i,i] = 0 y M[i,j] = * para todo i!=j (con esto estariamos diciendo que los Vi son conj. independientes, lo cual seria equivalente a ver si se puede colorear el grafo con m colores)