Edición de «Parcial del 16/05/15 (Algoritmos III)»

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

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} \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...
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>?
Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)

Plantilla usada en esta página: