Segundo Parcial 17/12/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 euleriano conexo de 9 vertices y 17 aristas. Sabiendo que los vertices ,, y aparecen 2 veces cada uno en el circuito euleriano de G, y 3 veces y 1 veces, determinar los posibles grados de y . Justificar.

Como el grafo es euleriano -> todos los vertices tienen grado par. Con lo cual si un vertice aparece k veces en el circuito, tiene que tener 2k ejes. Sabiendo esto y usando la suma de grados:
d(v) = 4*(2*2)+2*(2*3)+1*(2*1)+d(v8)+d(v9) = 2*m = 2*17
-> 30+d(v8)+d(v9)=34 -> d(v8)+d(v9)=4. Como deben tener grado par y no pueden estar aislados (el grafo es conexo) -> La unica posibilidad es que d(v8)=d(v9)=2


2) Probar que si I es un conjunto independiente maximo del grafo G de n vertices y R un recubrimiento minimo de las aristas, entonces |I| + |R| = n

Sale con esta propiedad: I es conj. indep. <=> V\I es recub. de ejes. Entonces
* n-|Imax| = |V\Imax| >= |Rmin| -> n-|Rmin| >= |Imax|
* n-|Rmin| = |V\Rmin| <= |Imax|
-> |Imax| <= n-|Rmin| <= |Imax| -> n-|Rmin| = |Imax| -> |Imax|+|Rmin|=n


3) Analizar el siguiente algoritmo para colorear el grafo G.

PASO 0: Poner c(i) = i para i = 1,..,n. Poner G' = G.
PASO 1: Mientras G' no sea un grafo completo repetir:
  PASO 2: Calcular, para todo par de vertices , 
          en G' tal que i < j,  y  no
          adyacentes en G' y c(i) = i y c(j) = j, s(i,j) = nro de adyacentes
          que tienen en comun  y 
  PASO 3: Sea , el par de vertices para el
          cual s(i,j) es maximo. Compactar  y 
          en un unico vertice  que tenga como adyacentes a los
          adyacentes de  mas los de .
          Poner G' = G' - {}
  PASO 4: Para todo k tal que c(k) = j poner c(k) = i
PASO 6: Parar, la funcion c define un coloreo de G y el numero de colores 
        usado es |G'|.

(a) Demostrar que el algoritmo produce un coloreo valido
(b) ¿Encuentra siempre un coloreo optimo? Justificar.
(c) Determinar la complejidad del algoritmo

a) Pareciera que si
b) Y.. no deberia (Por Grafos de Mycielski o algun delirio semejante)
c) Probablemente sea O(n^4)


4) En algunas redes practicas el flujo sufre alguna perdida durante la transmicion. Supongamos que tenemos el porcentaje de perdida por arco. ¿Como se puede adaptar el algoritmo de Ford & Fulkerson para encontrar flujo maximo en estas redes? Justificar. Dar un ejemplo.

Supongo que el porcentaje de perdida es x%. Multiplico todas las capacidades por 100-x. Ejecuto FF. Los flujos que quedan los divido por 100.


5) El problema de arbol generador de bajo grado es el siguiente: dado un grafo G y un entero k, ¿contiene G un arbol generador tal que todos los vertices en el arbol tienen ? ( significa grado en el arbol). Sabiendo que el problema de camino hamiltoniano en grafos es NP-completo, probar que este problema es NP-completo.

Saber si hay un camino hamiltoniano en G es equivalente a saber si hay un arbol generador de G con todos sus vertices de grado <= 2 (si es asi el arbol mismo es el camino hamiltoniano)