UEA: Diseño de Algoritmos
Trimestre: 2006 Invierno
Fecha: 10 de marzo de 2006

Instrucciones: Conteste cada una de las siguientes preguntas. Puede auxiliarse de programas de computadora pero no necesita entregarlos. Envíe sus respuestas usando pine a franz.

Problema 1: El problema del corte máximo es el de encontrar un subconjunto A de los vértices de una gráfica G = (V, E) tal que el costo total de las aristas que van de un vértice de A a un vértice que no está en A es tan grande como sea posible. El archivo corte.txt contiene la matriz de costos de una gráfica completa G con 100 vértices (numerados del 0 al 99 de arriba a abajo y de izquierda a derecha). Encuentre un subconjunto A (diga cuántos y cuáles vértices son) para el cual el costo del corte (dígalo) correspondiente sea tan grande como le sea posible. Evaluación: 5 puntos a la mejor solución, los demás obtendrán una calificación proporcional.

Problema 2: El problema del agente viajero es el de encontrar un circuito que visite exactamente una vez cada uno de los vértices de una gráfica G = (V, E) tal que el costo total de las aristas que forman el circuito es tan pequeño como sea posible. El archivo viaje.txt contiene la matriz de costos de una gráfica completa G con 100 vértices (numerados del 0 al 99 de arriba a abajo y de izquierda a derecha). Encuentre un circuito (diga en qué orden se visitan los vértices) con costo (dígalo) tan pequeño como sea posible. Evaluación: 5 puntos a la mejor solución, los demás obtendrán una calificación inversamente proporcional.

Problema 3: El problema del camino más largo es el de encontrar un camino que vaya de un vértice origen a un vértice destino de una gráfica G = (V, E) tal que no repita vértices y que el costo total de las aristas que lo forman sea tan grande como sea posible. El archivo largo.txt contiene la matriz de costos de una gráfica completa G con 100 vértices (numerados del 0 al 99 de arriba a abajo y de izquierda a derecha). Encuentre un camino (diga cuántos vértices lo forman y en qué orden se visitan) del vértice 0 al vértice 99 con costo (dígalo) tan grande como sea posible. Evaluación: 5 puntos a la mejor solución, los demás obtendrán una calificación proporcional.