Final del 27/02/15 (Algoritmos III)

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

Sea $G=(V,\quad E)$ un grafo tal que $G$ es isomorfo a $G^{c}$. Probar que $|V|\equiv 0\quad {\pmod {4}}$ o $|V|\equiv 1\quad {\pmod {4}}$.

Sugerencia: Como son isomorfos $m(G)=m(G^{c})$(Ejercicio 5.19.b) de las prácticas). Además, como son complementarios entre sí, sabemos que $m(G)+m(G^{c})={\frac {n(n-1)}{2}}$. 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 $m(G)$ como $m(G^{c})$ son números naturales).

Ejercicio 2

Sea $G=(V,\quad E)$ un grafo conexo y bipartito tal que $V_{1}\cup V_{2}=V$ y $V_{1}\cap V_{2}=\emptyset$. Probar que la bipartición es única.

Ejercicio 3

Sea $G=(V,\quad E)$ 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 $d$-regular y todas las regiones tienen grado $k$, 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), $dn=2m=kr$ (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 $m$ y $n$ en función de $d$, $k$ y $r$, y ponerlas en la ecuación de euler. Despejar $r$ en función de todo lo demás y observar que hay 5 pares $(d,k)$ tales que $r$ 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

Sea $G=(V,\quad E)$ un grafo y $L(G)$ su grafo de línea. Probar que para cualquier coloreo de $L(G)$, para todo $e\in V(L(G))$, a lo sumo hay 2 vecinos de $e$ que tienen el mismo color.

Sugerencia: Por absurdo, asumís que existe $e\in V(L(G))$ tal que, al menos, 3 vecinos utilizan el mismo color en un coloreo válido de $L(G)$, siendo la función de asignación de colores $f$. A partir de esto, tomar 3 vecinos de $e$, $e_{1},\quad e_{2},\quad e_{3}$ tales que $f(e_{1})=f(e_{2})=f(e_{3})$, 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 $(e_{i},\quad e_{j})\in E(L(G))$, $i\neq j$ dado que $e$ sólo tiene 2 extremos en $G$ 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

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

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