← Volver a los ejercicios

Armar un árbol a mano

Hay que dejar todos los barrios comunicados y gastar lo menos posible. Los tendidos se escogen de uno en uno, con un clic, y el que cierre un ciclo queda rechazado.

1. Antes de escoger

Grafo:

2. El tablero

Verde: los tendidos puestos. Dos barrios con el mismo relleno ya se alcanzan entre sí. Rojo punteado: el último rechazado.
Tendidos: Peso: Pedazos:

3. Qué tan cerca quedó

4. Para llevarse

Busque en el grafo de ocho barrios un tendido que no aparezca en ninguna selección de peso mínimo, y diga cómo lo reconoció sin correr ningún algoritmo. Después dibuje un grafo de cinco barrios en el que dos selecciones distintas lleguen al mismo peso mínimo.