# TDA | Practica 4 ejercicio 14 ## Consigna - Sea $q : V(G) \to \mathbb{Z}$ una función inyectiva para un grafo $G$. - Demostrar que $G$ tiene un único AGM $\iff$ el algoritmo de Kruskal con prioridad $q$ retorna el mismo árbol que el algoritmo de Kruskal con prioridad $-q$ ## Resolución - $G$ tiene un único AGM $\equiv A$ - el algoritmo de Kruskal con prioridad $q$ retorna el mismo árbol que el algoritmo de Kruskal con prioridad $-q$ $\equiv B$ - $A \iff B$ - Divido la demostración en partes: - $\Rightarrow)$ Quiero probar que $A \Rightarrow$ $B$, asumo $A$ verdadero - $\Leftarrow$) Quiero probar que $B \Rightarrow$ $A$, asumo $B$ verdadero - $\Leftarrow$) El algoritmo de kruskal con prioridad $q$ retorna el mismo árbol que el algo. Kruskal con prioridad $-q$ $\Rightarrow$ $G$ tiene un único arbol AGM. - Supongamos que $\exists \ 2$ AGM $\in G \ T_1 \ T_2$. - Siendo $w(T_1) \neq w(T_2)$. - Supongamos que el aplicarse Kruskal con $q$ queda seleccionado $T_1$, y con $-q$ se selecciona $T_2$. - Sí $T_1$ y $T_2$ tienen diferentes aristas, por lo menos hay una $e \in E(G) \land e \in E(T_1) \land e \not\in E(T_2)$ y viceversa. - Y también va a tener un orden de prioridad diferente según $q$ y $-q$. - Pero dado a que se asume a que $q$ y $-q$ llevan al mismo AGM, la existencia de diferentes $T$ lleva a la contradicción que ambos no pueden ser seleccionados por ambos esquemas de prioridad sin diferenciarse. - Esto contradice la hipotesis inicial de que varios $T$ son ambos AGM de $G$. - $\Rightarrow)$ - Asumo que $G$ tiene un único AGM. - O sea esto significa que cualquier conjunto de aristas que forme un AGM debe tener exactamente el mismo conjunto de aristas y el mismo peso total. - Asumo que $B$ es falso. - Es decir suponemos que $G$ tiene un único AGM, pero kruskal con $q$ y con $-q$ dan resultados sdiferentes $T_1, T_2$ - Dado que $G$ tiene un único AGM (Proposición $A$), cualquier algoritmo correcto que genere un AGM debe resultar en ese mismo conjunto único de aristas. - Pero supuse que los resultados son diferentes $T_1 \neq T_2$. Esto implicaría que uno de los $T$ **NO ES UN AGM**, lo cual hace absurda nuestra suposición inicial $A$. $\square$