Prueba de Selección de Equipos de Alemania 2005 Problema 2

2 Sea $M$ un conjunto de puntos en el plano cartesiano, y sea $\left(S\right)$ un conjunto de segmentos (cuyos extremos no necesariamente tienen que pertenecer a $M$ ) tal que se puede caminar desde cualquier punto de $M$ hasta cualquier otro punto de $M$ viajando a lo largo de segmentos que están en $\left(S\right)$ . Halle la menor longitud total de los segmentos de $\left(S\right)$ en los casos a.) $M = \left\{\left(-1,0\right),\left(0,0\right),\left(1,0\right),\left(0,-1\right),\left(0,1\right)\right\}$ . b.) $M = \left\{\left(-1,-1\right),\left(-1,0\right),\left(-1,1\right),\left(0,-1\right),\left(0,0\right),\left(0,1\right),\left(1,-1\right),\left(1,0\right),\left(1,1\right)\right\}$ . En otras palabras, halle los árboles de Steiner del conjunto $M$ en los dos casos anteriores. darij

0

0

Kevin

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados