Edición de «Práctica 6: Árboles (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 107: | Línea 107: | ||
<br> Sea K = {k1,..,k(n-1)} el AG de Kruskal. Sup. que no es minimo | <br> Sea K = {k1,..,k(n-1)} el AG de Kruskal. Sup. que no es minimo | ||
<br> T es AGM y ei <= ei+1 "mas parecido a K" (K∩T) es maxima) | <br> T es AGM y ei <= ei+1 "mas parecido a K" (K∩T) es maxima) | ||
<br> | <br> Sea i minimo / ei != ki, G = T+{ki} | ||
<br> G tiene exactamente un ciclo C (ej 6.2 b). Como T es aciclico -> ki en C | <br> G tiene exactamente un ciclo C (ej 6.2 b). Como T es aciclico -> ki en C | ||
<br> Sea eMAX el eje maximo de C. Como ki no forma un ciclo con e1,..,ei-1 -> eMAX != ki | <br> Sea eMAX el eje maximo de C. Como ki no forma un ciclo con e1,..,ei-1 -> eMAX != ki |