DAA Proyecto 2. Broken Phone

Orientación: Sin imaginación

Kevin estaba leyendo un libro sobre Diseño y Análisis de Algoritmos cuando se topó con un problema que llamó su atención. El texto era el siguiente:

Se tiene un grafo bipartito $G$ con $U$ nodos en el la primera parte y $V$ nodos en la segunda parte. Un subgrafo de $G$ está $k-cubierto$ si todos sus nodos tienen al menos grado $k$. Un subgrafo $k-cubierto$ es mínimo si su cantidad de aristas es la mínima posible. Encuentre el mínimo grafo $k-cubierto$ para todo $k$ entre $0$ y $MinDegree$ (grado mínimo del grafo $G$). Luego de entender el problema, automáticamente pensó dos cosas:

• Quiero resolver este problema.
• ¿A los profesores se les habrá acabado la imaginación para los textos de los proyectos?