# TDA | Practica 4 ejercicio 13 ## Consigna - $13.\star$El algoritmo de Kruskal (resp. Prim) con orden de selección es una variante del algoritmo de Kruskal (resp. Prim) donde a cada arista $e$ se le asigna una prioridad $q(e)$ además de su peso $p(e)$. Luego, si en alguna iteración del algoritmo de Kruskal (resp. Prim) hay más de una arista posible para ser agregada, entre esas opciones se elige alguna de mínima prioridad. - a) Demostrar que para todo árbol generador mínimo $T$ de $G$, si las prioridades de asignación están definidas por la función. $$q_T(e)=\begin{cases}0&\text{si }e\in T\\1&\text{si }e\notin T\end{cases}$$ - b) entonces se obtiene $T$ como resultado del algoritmo de Kruskal (resp. Prim) con orden de selección ejecutado sobre $G$ (resp. cualquiera sea el vértice inicial en el caso de Prim) Usando el inciso anterior, demostrar que si los pesos de $G$ son todos distintos, entonces $G$ tiene un único árbol generador mínimo. ## Resolución ### a) - Por cada arista del grafo tiene peso y prioridad. - Entonces en las iteraciones de kruskal si hay más de una arista posible para agregar, se elige la de menor prioridad. - Podemos pensar como en los algoritmos de sorting, es un factor de ordenamiento secundario para definir desempates. - $q$ viene de queue, o sea es una cola. - Entonces $q_t(e)$ significa la posición de la arista $e$ en la cola de $T$. - Nos dice que sí $e$ pertenece al arbol, dejalo en cero. - Y si no pertenece, dejalo en uno. - Entonces $min(0,1) = 0$. - Esto garantiza que $\forall e \in E(T)$ tiene que tener la minima prioridad. - Prioridad y formación de $T$: Esta asignación de prioridades no solo afecta la selección de aristas durante las iteraciones del algoritmo, sino que también garantiza que el árbol generador mínimo $T$ se forma con las aristas de menor prioridad posible. En el caso de aristas con el mismo peso, la prioridad se convierte en el factor decisivo. ### b) - Quiero demostrar que: - Si los pesos de $G$ son todos distintos - Entonces G tiene un único arbol - $(\forall e \in E(T) \Rightarrow \forall j \in E(T)) \Rightarrow (w(e) \neq w(j)) \Rightarrow G$ **tiene un único árbol**. - Pensando un rato la proposición, tiene mucho sentido. - Supongo que si los pesos de $G$ son todos distintos, entonces $G$ tiene más de un AGM. - Supongamos también que en el grafo $G$, hay 2 AGM diferentes entre sí, $T_1$, y $T_2$ - Esto significa que por lo menos la diferencia entre ellos tiene que ser de una arista. - Designamos $e_1 \in T_1 \land e_2 \in T_2$ - Pero Por definición, un AGM incluye aristas que en conjunto suman el peso mínimo posible para conectar todos los vértices. Dado que todos los pesos son distintos, $e_1$ y $e_2$ no pueden tener el mismo peso. - Entonces si tienen que tener una arista de diferencia y todos los pesos son distintos eso implica que una va a ser más pesada que la otra no siendo un AGM y esto es absurdo. - Sin pérdida de generalidad, supongamos que $w(e_1) < w(e_2)$. Esto implica que si $e_2$ fuese parte de un AGM, entonces reemplazar $e_2$ en $T_2$ por $e_1$ reduciría el peso total de $T_2$, lo que contradice la suposición de que $T_2$ es un AGM. Por lo tanto, $T_2$ no podría ser un AGM si $w(e_1) < w(e_2)$. $\square$