Quiero demostrar que la salida del algoritmo de Kruskal es un árbol de expansión.
Sea $G$ sea un grafo conexo y ponderado y sea $S$ sea el subgrafo de $G$ que es la salida del algoritmo. $S$ no pueden formar un ciclo y $S$ debe estar conectada, ya que la primera arista que une dos componentes de $S$ habría sido añadido por el algoritmo.
Por lo tanto, concluimos que $S$ es un árbol de expansión de $G$ .
¿Es ésta una justificación completa y correcta? ¿Puedo cambiar algo para mejorarla?
Para demostrar la corrección del algoritmo de Kruskal, tenemos que demostrar que genera un árbol de expansión y que este árbol de expansión es mínimo . Sea $S$ sea el subgrafo de $G$ que es la salida del algoritmo de Kruskal.
Primero demostramos que genera un árbol de expansión. Un árbol de expansión debe ser
$S$ debe ser conexo (y contener todos los vértices de $G$ ), porque de lo contrario el algoritmo no habría terminado. Además, $S$ debe ser acíclica, porque cada vez que se añade una arista, esa arista no debe crear ciclos. Por lo tanto, el algoritmo de Kruskal produce un árbol de expansión.
A continuación demostramos que este árbol de expansión es mínimo. Supongamos por contradicción que $S$ no es mínimo. Entonces debe existir un árbol de mínima expansión (MST) con aristas que no estén en $S$ . Elija el MST con el menos número de aristas que no están en $S$ y llamar a esto $T$ .
Consideremos ahora la arista $e$ que fue la primera arista que se añadió a $S$ por el algoritmo de Kruskal y que no está en $T$ . Entonces $T \cup \{e\}$ debe contener un circuito, y como $S$ no tiene circuitos, una de las aristas del circuito no debe estar en $S$ . Llama a este borde $f$ . Entonces $T' = (T \cup \{e\}) \setminus \{f\}$ también es un árbol de expansión.
Desde $T$ es un MST, tenemos que $w(e) \geq w(f)$ . Además, puesto que $e$ fue elegido por el algoritmo de Kruskal, debe tener un peso mínimo, por lo que $w(e) \leq w(f)$ lo que a su vez implica que $w(e) = w(f)$ . Por lo tanto, $T'$ también es un MST, pero tiene una arista más en común con $S$ que $T$ pero habíamos elegido $T$ tal que tenga el mayor número de aristas en común con $S$ por lo que llegamos a una contradicción. Concluimos que $S$ es mínima.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
