Tarea 10 de Análisis y Diseño de Algoritmos

Trimestre 2014 Invierno
Entrega: 17 de marzo de 2014 antes de las 22:00

Considere los siguientes dos problemas:
Estos dos problemas son NP completos. Una forma de transformar CV en CQ está dada por el siguiente resultado: U es una cubierta por vértices de G si y sólo si W = V-U es un clan en el complemento de G.

Escribe un programa llamado cvacqZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) que lea una instancia de CV y la transforme en una instancia equivalente de CQ. La entrada consiste de dos enteros N y K seguida de la matriz de adyacencia de una gráfica G con N vértices. La salida consiste de dos enteros N y J seguida de la matriz de adyacencia de una gráfica H con N vértices. J y H deben ser tales que las respuestas CV(G, K) y CQ(H, J) deben ser iguales.

Ejemplo de entrada
 Ejemplo de salida
5 3
0 1 1 0 0
1 0 1 0 1
1 1 0 1 1
0 0 1 0 1
0 1 1 1 0
 5 2
0 0 0 1 1
0 0 0 1 0
0 0 0 0 0
1 1 0 0 0
1 0 0 0 0

Notas: Sus programas no deben leer ni escribir nada adicional a lo que se indica en el enunciado. El tiempo de ejecución de sus algoritmos será considerado como parte de la evaluación.