PUERTA | PUERTA CS 2012 | Pregunta 27

Sea G un grafo ponderado con pesos de aristas mayores que uno y G’ sea el grafo construido elevando al cuadrado los pesos de las aristas en G. Sean T y T’ los árboles generadores mínimos de G y G’, respectivamente, con pesos totales t y T’. ¿Cuál de las siguientes afirmaciones es verdadera?
(A) T’ = T con peso total t’ = t ²
(B) T’ = T con peso total t’ < t ²
(C) T’ != T pero peso total t’ = t ²
(D) Ninguno de lo anterior

Respuesta: (D)
Explicación: Elevar al cuadrado los pesos de los bordes en un gráfico ponderado no cambiará el árbol de expansión mínimo. Suponga lo contrario para obtener una contradicción. Si el árbol de expansión mínima cambia, al menos una arista del antiguo gráfico G en el antiguo árbol de expansión mínima T debe ser reemplazada por una nueva arista en el árbol T’ del gráfico G’ con pesos de arista cuadrática. La nueva arista de G’ debe tener un peso menor que la arista de G. Esto implica que existen unos pesos C1 y C2 tales que C1 < C2 y C12 >= C22. Esto es una contradicción.
Fuente:  http://www.cs.nyu.edu/courses/spring06/V22.0310-001/hw3.htm

Las sumas de cuadrados de dos o más números siempre son menores que el cuadrado de la suma.
Ejemplo: 2^2 + 2^2 < (4)^2

Pero

there is one counter example when the graph has only one edge.  
         In that case, the two values are same. 

Cuestionario de esta pregunta