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 Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v_1,...,v_9} y 17 aristas. Sabiendo que los vertices Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v_1} ,, 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 Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v_j}
 no
          adyacentes en G' y c(i) = i y c(j) = j, s(i,j) = nro de adyacentes
          que tienen en comun Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v_i}
 y Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v_j}

  PASO 3: Sea Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v_i}
,Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v_j}
 el par de vertices para el
          cual s(i,j) es maximo. Compactar Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v_i}
 y Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v_j}

          en un unico vertice Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v_i}
 que tenga como adyacentes a los
          adyacentes de Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v_i}
 mas los de Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v_j}
.
          Poner G' = G' - {Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v_j}
}
  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 Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle grado_T \le k} ? (Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle grado_T} 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)