Edición de «Parcial del 16/05/15 (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 36: | Línea 36: | ||
Dado un grafo conexo <math>G</math> con pesos asociados a sus ejes, un árbol generador máximo de <math>G</math> es un árbol generador de <math>G</math> que tiene peso máximo entre todos los árboles generadores de <math>G</math>. | Dado un grafo conexo <math>G</math> con pesos asociados a sus ejes, un árbol generador máximo de <math>G</math> es un árbol generador de <math>G</math> que tiene peso máximo entre todos los árboles generadores de <math>G</math>. | ||
Sea <math>G</math> un grafo conexo en el cual cada eje <math>e</math> tiene asociado un peso no necesariamente positivo <math>p(e) \in \mathbb{R}</math>. Dada una función <math> f: \mathbb{R} | Sea <math>G</math> un grafo conexo en el cual cada eje <math>e</math> tiene asociado un peso no necesariamente positivo <math>p(e) \in \mathbb{R}</math>. Dada una función <math> f: \mathbb{R} /rightarrow \mathbb{R}</math>, definimos <math>G_f</math> como el grafo que tiene los mismos vértices y ejes que <math>G</math>, pero en el cual cada eje <math>e</math> tiene asociado el peso <math>f(p(e))</math> en vez de <math>p(e)</math>. Sea <math>T</math> un árbol generador de <math>G</math>, el cual por definición también lo es de <math>G_f</math>, y cuyo peso total en cada grafo es la suma de los pesos asociados a sus ejes en ese grafo. ¿Es cierto que... | ||
(a) para <math>f(x) = x + b</math>, <math>T</math> es un árbol generador mínimo de <math>G</math> si y sólo si T es un árbol generador mínimo de <math>G_f</math>? | (a) para <math>f(x) = x + b</math>, <math>T</math> es un árbol generador mínimo de <math>G</math> si y sólo si T es un árbol generador mínimo de <math>G_f</math>? |