Segundo Parcial 08/08/2005 (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 de n vertices tal que para todo vertice v se cumple que d(v) d.
Demostrar que (G)

Sea Ck = {v/ v tiene color k}.
Supongamos |Ck| > n-d . Tomo v perteneciente a Ck => v tiene x vecinos que no pertenecen a Ck . x < n -(n-d) = d => d(v)<d => Abs.
=> Cada conjunto de colores tiene <= (n-d) vertices
n = i=1 a X(G) |Ck| <= i=1 a X(G)max{|Ck|} = x(G)*max{|Ck|} <= x(G)*(n-d)


No revise la dem muy a fondo, tiene pinta que esta bien. pero a mi se me ocurrio otra cuando pense el ejercicio. Supongamos Cardinalidad del conjunto indep. maximo.
Entonces vale que, , ya que cada color a lo sumo tiene cardinalidad igual a la del conj. indep. maximo.
ahora , ya que cada uno de los grados son mayores a d, en el conj. indep. cada vertice tiene a lo sumo n-d vertices no adyacentes.
Por lo tanto


2) Determinar los valores de m y n para los cuales los siguientes grafos tienen un circuito euleriano. Idem para circuito hamiltoniano. Justificar
(a) ;
(b)


a) Kn: circ. euleriano para todo n>1 impar, circ. hamiltoniano para todo n>2
b) Kmn: circ. euleriano para todo m>1 y n>1 ambos pares, circ. hamiltoniano para m=n (m>1 y n>1)



3) (a) Sea G un bosque de 8 o mas vertices. Demostrar que el grafo complemento de G no es planar.
(b) Presentar un bosque de 7 vertices tal que su complemento sea planar. Justificar

a) Para bosques de 9 o mas vertices vale, ya que es un grafo bipartito y en una de las particiones habra al menos 5 vertices (con lo cual hay un K5 en el complemento). Para el caso de 8 vertices lo vemos por nuestro gran amigo, el absurdo:
Sup. Gc es planar. Como G es bosque -> m(G) <= n-1, y como Gc es planar -> m(Gc) <= 3*n-6
-> m(Gc) = n(n-1)/2 - m(G) <=> n(n-1)/2 = m(Gc) + m(G) <= 3*n-6 + n-1 = 4*n-7
-> Reemplazando con 8: 8*7/2 <= 4*8-7 <=> 28 <= 25 (Claramente ABS)


<otra forma>

si G bosque entonces tiene una unica region

y como r = m - n + c + 1 por Euler (c = comp. conexas)

vale 1 = m - n + c + 1 que equivale a m = n - c

luego sea mc = la cantidad de ejes Gc (G complemento)

se que mc = n(n-1)/2 - m q equivale a ...

mc = n(n-1)/2 - (n - c)

mc = n(n-1)/2 - n + c

no se cuantas comp conexas tendra G pero seguro q es mas de una

por lo tanto puedo acotar a c >= 1

luego mc = n(n-1)/2 - n + c >= n(n-1)/2 - n + 1

     mc => n(n-1)/2 - n + 1    (a)

bueno voy a suponer que Gc es planar y por teo si un grafo con k comp. conexas es planar cumple que m <= 3n - 6k asi q mc <= 3n - 6k para que sea planar y como vale q ...

n(n-1)/2 - n + 1 <= mc <= 3n - 6k
n(n-1)/2 - n + 1 <= 3n - 6k esto deberia valer si es q Gc es planar

pero ademas yo se por un ejer de la practica que si un grafo es bosque entc su complemento es conexo. Asi que k = 1 en este caso

asi q tenmos que para q Gc sea planar deberia almenos cumplir que :

n(n-1)/2 - n + 1 <= 3n - 6.1 (b)

veamos para que valores de n se cumple la desigualdad (b)


En fin esa desigualdad vale para 2 <= n <= 7 , es decir que no vale para n >= 8 y por lo tanto Gc no es planar.

( osea llegamos a que algo q es mas chico q el mismo mc (a), para n => 8 no es menor o igual a 3n -6 ni a palos , es decir q si supieramos el verdadero valor de mc todavia seria aun mayor q (a) y por lo tanto tampoco seria menor a 3n - 6 y luego no seria planar )

link a wolframalpha con la solucion de la desigualdad (b) http://www.wolframalpha.com/input/?i=n%28n-1%29%2F2++-+n+%2B1+%3C%3D+3n+-+6


b) Despues lo dibujo


4) A,B,C,D,E y F son agentes secretos. Algunos de ellos deben reunirse de a pares en un reducto subterraneo para intercambiar informacion. Por razones de seguridad solo un par de agentes puede reunirse al mismo tiempo. Asimismo se ha decidido que por cada reunion(excepto la ultima), uno de los agentes que participen en la misma tambien debe participar en la siguiente. A continuacion aparecen en un orden arbitrario los pares de agentes que deben reunirse: A con B, A con F, B con C, B con D, B con E, C con E, C con F, D con F, E con F. Modelar la situacion como un problema sobre grafos y encontrar una sucesion de reuniones que cumpla con los requerimientos. Justificar.

Hay que encontrar un camino hamiltoniano entre los vertices (cada vertice es un par de agentes que se reunen, y cada eje determina si hay un agente de una reunion que puede estar en otra)


5) Sean y los siguientes problemas.

: SET PACKING
Entrada: una familia finita F de conjuntos finitos y un entero positivo k.
Pregunta: ¿F contiene k o mas conjuntos disjuntos de a pares?
: CONJUNTO INDEPENDIENTE MAXIMO
Entrada: un grafo G y un entero positivo k
Pregunta: ¿G contiene un conjunto independiente de k o mas nodos?
(a) Demostrar que si P entonces P.
(b) Demostrar que si NP-completo entonces NP-completo.



a) Basta con hacer una reducción de Pi_2 a Pi_1 para ver que Pi_2 es de la misma o menor clase de complejidad que Pi_1, por lo que si Pi_1 es P, Pi_2 también lo es. La fórmula de reducción de Pi_2 es: convertir G a su grafo de lineas, y cada conjunto de F son las aristas que son incididas por un nodo. Luego en Pi_1 estás buscando el conjunto disjunto que incide sobre todas las aristas posibles, con k o más conjuntos (nodos).

b) Creo que con demostrar que Pi_1 es verificable en tiempo polinómico y que hay una reducción de Pi_2 a Pi_1, y sabemos que Pi_2 es P, entonces Pi_1 es NP-completo.


b) hay que demostrar que Pi_2 pertenece a NP. Luego una trans. polinomica de Pi_1 a Pi_2 . De esta forma tenemos las dos cosas para decir que Pi_2 es NP-completo. Osea Pi_2 es NP y para todo Pi en NP se lo puede transformar a Pi_2. Bueno pero eso ya valia para Pi_1, osea es NP y todo problema en NP se lo puede transformar a Pi_1, pero como tenemos una transformacion de Pi_1 a Pi_2. Aca en el parcial faltaria demostrar que Pi_1 devuelve "si" si y solo si f(Pi_1) devuelve "si". La reduccion tiene que ser polinomial.