Practico 6, ejercicio 3 parte a) ii)

Practico 6, ejercicio 3 parte a) ii)

de Camilo Ferrero Alvarez -
Número de respuestas: 1

Hola buenas,

Me gustaria saber si esta demostracion es valida.

Lema.: Si \widetilde e \in E \backslash T entonces \widetilde e no pertenece a ningun MST de G'

Demo.:
Si \tilde e \notin T entonces T \cup \{\tilde e\} tiene un unico ciclo del que \tilde e es la mas costosa, pues de no ser asi, si eliminaramos la mas costosa no habria ciclo en T y por ende \tilde e \in T.
Como \tilde e es la arista mas costosa de un ciclo en un subgrafo de G (T \cup \{\tilde e\}) lo es entonces tambien lo es del grafo completo G y como G es un subgrafo de G' entonces \tilde e es la arista mas costosa de un ciclo en G' y por ende no pertenece a ningun MST de G'. _\blacksquare

Como todo arbol tiene |V| - 1 aristas tenemos que si existe otro arbol \widetilde T que sea MST y tenga una arista que no pertenece a T' entonces este no tiene una arista e_j que pertenece a T'.

Sea \tilde e \in \widetilde T y \tilde e \notin T'

\tilde e \neq e_{max} porque por 4.20 no pertenece a ningun MST.

Caso e \notin T':

En este caso la nueva arista e era la mas pesada del ciclo es decir e =e_{max} luego T' = (T \cup \{e\}) \backslash \{e\} = T por lo que como \tilde e \neq e_{max} = e y \widetilde e \notin T' = T entonces \widetilde e \in E \backslash T y por el lema es absurdo.

Caso e \in T':

Como este caso no eliminamos e existe un e_i \in T : e_i \notin T'

Luego sabemos que \tilde e \neq e pues esta esta en T' y ademas sabemos que \tilde e \neq e_i = e_{max}

Por lo tanto como T' = (T \cup \{e\}) \backslash \{e_i\} tenemos que los nodos que no estan en T' son E\backslash T \cup \{e_i\} y como \tilde e \neq e_i tenemos que \tilde e \in E \backslash T lo cual es absurdo por el lema.

Por lo tanto es absurdo suponer que existe un MST de G' que difiera en una arista, consecuentemente todo MST de G' debe tener las mismas |V| - 1 aristas que T', por lo cual T' es MST de G'. _\blacksquare

Saludos,

Camilo.
En respuesta a Camilo Ferrero Alvarez

Re: Practico 6, ejercicio 3 parte a) ii)

de Fernando Fernandez -
Hola Camilo.
Está muy bien el lema. Y ahí ya casi tenías todo. El resto parece corresponder a un intento diferente de demostración, aunque parece correcto.

Con el lema habías descartado todas las aristas en E \setminus T como posibles aristas de un MST de G'. Quedan como posibles candidatas las n-1 aristas de T, y e. Una de ellas es e_{\max}, que como explicás más abajo, y por la misma propiedad 4.20, tampoco puede pertenecer a un MST de G'. Por lo tanto, las únicas posibles aristas de un MST son las n-1 aristas en (T \cup \{e\}) \setminus e_{\max}, y esto es T'. Podrías agregar la demostración de que T' es un árbol (grafo conexo y acíclico) y que es de cubrimiento de G'.

Algunos detalles.
Pusiste "todo árbol tiene \vert V\vert - 1 aristas". En realidad, un árbol puede tener menos aristas, incluso 0 (un árbol hoja). Debés haber querido poner árbol de cubrimiento. En esa misma frase, cuando ponés "este" me parece que querés decir \tilde{T}. Pero en realidad, por como está redactado, "este" sería T'. Te sugiero que en lo posible evites los "este", "ese", "aquel", etc. De todas formas no parece que hagas uso de esa afirmación.

Más abajo donde dice "los nodos que no están en T'" seguramente quisiste decir "las aristas".