Final del 27/02/15 (Algoritmos III)

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

Final semi-libre tomado en la fecha 27/02/2015 tomado por Javier Marenco. El final constaba de 6 ejercicios a ser resueltos por escrito.


Ejercicio 1[editar]

Sea un grafo tal que es isomorfo a . Probar que o .

Sugerencia: Como son isomorfos (Ejercicio 5.19.b) de las prácticas). Además, como son complementarios entre sí, sabemos que . Utilizar la primer igualdad en la segunda y ver que debe ocurrir para que la divisón obtenida sea un número natural (que debe serlo ya que tanto como son números naturales).

Ejercicio 2[editar]

Sea un grafo conexo y bipartito tal que y . Probar que la bipartición es única.

Ejercicio 3[editar]

Sea un grafo platónico, es decir un grafo 3-conexo (conexo y que entre todo par de vértices haya, al menos, 3 caminos dijuntos), planar, regular y todas sus regiones con igual cantidad de aristas. Probar que sólo hay 5 grafos platónicos.

Sugerencia: Sin pérdida de generalidad, se puede suponer que el grafo es -regular y todas las regiones tienen grado , por definición de grafo platónico. La idea era obtener igualdades a partir de propiedades: fórmula de euler (por ser conexo y planar), (sumatoria de grados de los nodos igual a 2m y utilizar que el grafo es regular, sumatoria de grado de las regiones igual a 2m y utilizar que todas las regiones tienen k aristas). Despejar ambos y en función de , y , y ponerlas en la ecuación de euler. Despejar en función de todo lo demás y observar que hay 5 pares tales que es un natural válido. Finalmente, se debería demostrar que para cada par hay un grafo platónico y que es único (que todos son isomorfos a él), pero no era la idea del ejercicio.

Ejercicio 4[editar]

Sea un grafo y su grafo de línea. Probar que para cualquier coloreo de , para todo , a lo sumo hay 2 vecinos de que tienen el mismo color.

Sugerencia: Por absurdo, asumís que existe tal que, al menos, 3 vecinos utilizan el mismo color en un coloreo válido de , siendo la función de asignación de colores . A partir de esto, tomar 3 vecinos de , tales que , entonces ninguno de los 3 es vecino entre sí ya que sino no sería un coloreo válido. Aplicando la definición de grafo de línea, se puede ver que algún , dado que sólo tiene 2 extremos en por ser arista del mismo. Con lo cuál se llega a un absurdo y lo contrario a lo asumido debe ser cierto.

Ejercicio 5[editar]

Se pide resolver el siguiente problema con un algoritmo polinomial: se tiene un conjunto de clases y una cantidad de aulas k. Cada clase tiene un horario de inicio y otro de fin, lógicamente no se puede dictar 2 clases en una misma aula si las mismas se superponen en horarios. Se quiere saber si la cantidad de aulas son suficientes para dictar todas las clases en un mismo día.

Sugerencia: Es un problema conocido de scheduling que seguro está mejor explicado en alguna fuente de internet. Cualquiera que quiera aportar una fuente o explicarlo con sus palabras, es más que bienvenido.

Ejercicio 6[editar]

Demostrar que un problema era NP-Hard. La idea era proponer un candidato perteneciente a NP-Completo o a NP-Hard (seguramente, de los problemas vistos en la materia) tal que se reduce polinomialmente a y con eso alcanzaba, de acuerdo a la definición de NP-Hard vista en la materia.