Buenas, quería saber si este ejercicio está resuelto correctamente. Adjunto mi solución.
Gracias!
Buenas,
Al principio, debería decir: "Sabemos que T es un árbol".
En el tercer renglón, no es correcto cuando se dice que e_max, la arista de costo máximo del ciclo formado al agregar e a T, pertenece al camino en T, porque e_max puede ser e.
Falta tener en cuenta ese punto en la demostración 1).
En 2) basta con mostrar que todas las aristas de E'\T' no pueden pertenecer a ningún MST. Es decir, {e_max} U {E\T}. El argumento de e_max está bien. Para E\T, basta con mostrar que en G' están todos los mismos ciclos que en G, entonces las aristas de E\T también son la arista de mayor costo en algún ciclo en G'.
En la parte b) hay que ser más específico con "recorrer el ciclo", para esto hay que utilizar algún algoritmo de recorrida de grafos. El análisis del tiempo de ejecución le falta detalle. Hay que decir qué estructuras de datos se utilizan, y cómo cada paso del algoritmo lleva a ese tiempo.
Saludos,
Guillermo
Al principio, debería decir: "Sabemos que T es un árbol".
En el tercer renglón, no es correcto cuando se dice que e_max, la arista de costo máximo del ciclo formado al agregar e a T, pertenece al camino en T, porque e_max puede ser e.
Falta tener en cuenta ese punto en la demostración 1).
En 2) basta con mostrar que todas las aristas de E'\T' no pueden pertenecer a ningún MST. Es decir, {e_max} U {E\T}. El argumento de e_max está bien. Para E\T, basta con mostrar que en G' están todos los mismos ciclos que en G, entonces las aristas de E\T también son la arista de mayor costo en algún ciclo en G'.
En la parte b) hay que ser más específico con "recorrer el ciclo", para esto hay que utilizar algún algoritmo de recorrida de grafos. El análisis del tiempo de ejecución le falta detalle. Hay que decir qué estructuras de datos se utilizan, y cómo cada paso del algoritmo lleva a ese tiempo.
Saludos,
Guillermo