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 131: | Línea 131: | ||
==Ejercicio 06.22:== | ==Ejercicio 06.22:== | ||
<pre> | <pre> | ||
Lema 1: T es | Lema 1: T es arbol y e no en E -> T+e tienen un ciclo C que contiene a e | ||
Dem: | Dem: | ||
e = (u,v). T es conexo -> Ex. camino C1 entre u y v. En T+e, C1+e forman un circuito que | e = (u,v). T es conexo -> Ex. camino C1 entre u y v. En T+e, C1+e forman un circuito que inclute a e. | ||
Lema 2: T es | Lema 2: T es arbol, T+e tiene un ciclo, T+e-e'con e y e' en C -> T+e-e' es arbol | ||
Dem: | Dem: | ||
* E(T+e-e') = n-1 + 1 - 1 = n-1 | * E(T+e-e') = n-1 + 1 - 1 = n-1 | ||
* Sup e'=(w1,w2). T+e tiene un ciclo que incluye a e' -> Ex. 2 caminos en T+e entre w1 y w2 -> T+e-e' tiene un camino entre w1 y w2 -> no se desconecto nada -> T+e-e' es conexo | * Sup e'=(w1,w2). T+e tiene un ciclo que incluye a e' -> Ex. 2 caminos en T+e entre w1 y w2 -> T+e-e' tiene un camino entre w1 y w2 -> no se desconecto nada -> T+e-e' es conexo | ||
-> T+e-e' es | -> T+e-e' es arbol | ||
</pre> | </pre> | ||
<br> Sup. que G tiene 2 AGMs, S y T -> | <br> Sup. que G tiene 2 AGMs, S y T -> Habra ejes en S y no en T, y viceversa | ||
<br> Sea | <br> Sea eS el menor eje que esta en S y no en T ->(Lema 1) T+eS tiene un ciclo C que contiene a eS | ||
<br> En C Ex. eT en T que no esta en S (en S no habia ciclos). Por HI l(eS) != l(eT) | |||
<br> Puede pasar que l(eS) > l(eT)? ABS (por ser el menor eje) -> l(eS) < l(eT) | |||
<br> En C Ex. eT en T que no esta en S (en S no | |||
<br> Puede pasar que l( | Nota: Me parece que este ABS es fruta, es el menor eje de S, a priori no sabes nada de T... | ||
Lo mejor es correr o generar el arbol generador minimo con kruskal aprovechando que al ser todos los ejes distintos kruskal se vuelve deterministico y no puede dar dos arboles distintos. | |||
<br> -> l(T+eS-eT) = l(T)+l(eS)-l(eT) < l(T) -> AG es mas chico que T (ABS) | |||
<br> -> Ex. Unico AGM | |||
==Ejercicio 06.23:== | ==Ejercicio 06.23:== |