Buenas tardes,
Estoy trabajando en el ejercicio 3 parte a. Pero me encuentro con un problema en la prueba en el cual estoy trancado. Les hablo con la intención de que me puedas ayudar a continuar.
En particular el problema es probar que T' es e efecto el grafo con el menor "coste".
Es claro que si añadimos la arista e en el grafo, TODOS los arboles pueden disminuir su actual coste, ya que al añadir 'e' a G genera un ciclo, y sabemos que el mayor elemento de dicho ciclo debe ser eliminado por el teorema 4.20. Por lo que generamos un nuevo árbol pero ahora con un costo menor.
EL problema es ver que efectivamente T' es el árbol con el menor de los costes en G'.
Por lo tanto, debería suceder que para todo árbol R en G, Costo (R) - costo (r_max) >= Costo (T) - costo (e_max) = Costo (T'). Donde r_max es la arista con mayor coste en el ciclo que genera e en R.
No se si esto es por donde debería ir, pero la verdad es que probé de todas formas demostrar esto pero no llego a nada.
Les pido ayuda con esto.
Saludos y gracias
Daniel