Parcial del 04/07/15 (Algoritmos III)

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

Ejercicio 1[editar]

Dada una representación planar de un grafo planar , se define a su (pseudo-multi) grafo dual de la siguiente manera: por cada región de la representación planar de se agrega un vértice en ; por cada eje de la representación planar de se agrega un eje en entre los vértices correspondientes a las regiones que están a ambos lados de en . Un grafo planar se dice autodual si es isomorfo a su dual.

Exhibir todos los árboles no isomorfos autoduales. Justificar.

Ejercicio 2[editar]

Sea un grafo de ejes.

(a) Demostrar que , donde es la cantidad de vértices de un subgrafo completo máximo de .

(b) Demostrar que , donde es .

Ejercicio 3[editar]

Supongamos que se dispone de un algoritmo que dado un grafo y un entero , informa en tiempo polinomial si el grafo tiene un conjunto independiente formado por o más vértices. En base a ese algoritmos, diseñar un nuevo algoritmo que dado un grafo de vértices, encuentre en tiempo polinomial un conjunto independiente máximo de . El algoritmo propuesto deve invocar al algoritmo original veces. Mostrar que el algoritmo propuesto es correcto y determinar la cantidad de veces que invoca al algoritmo original. Justificar. La cantidad de veces que el mejor algoritmo que conocemos invoca al algoritmo original es , lo cual es necesario para obtener puntaje máximo en este ejercicio.

Ejercicio 4[editar]

Demostrar detalladamente que alguno de los siguientes problemas es NP-completo usando que el otro lo es. Indicar claramente cuál problema se intenta demostrar que es NP-completo y cuál se supone que lo es.

: CAMINO HAMILTONIANO

Entrada: grafo
Pregunta: ¿existe un camino que pasa exactamente una vez por cada vértices de ?

: CAMINO MÁXIMO

Entrada: grafo de vértices; tal que .
Pregunta: ¿tiene un camino simple de o más ejes?

Ejercicio 5[editar]

Sea un grafo. Demostrar que son equivalentes:

(a) tiene ejes, y es arbitrariamente atravesable desde todos sus vértices.

(b) no tiene vértices aislados, y es arbitrariamente atravesable desde al menos tres vértices distintos.

(c) tiene circuitos simples, y todos ellos son hamiltonianos.

(d) es (ciclo simple de vértices).

SUGERENCIA: Salen y , entre otras.