Árbol de expansión mínimo: ¿Qué es exactamente la propiedad de corte?

Question

He pasado mucho tiempo leyendo presentaciones en línea y libros de texto sobre la propiedad de corte de un árbol de expansión mínimo. Realmente no entiendo lo que se supone que debe ilustrar o incluso por qué es práctico. Supuestamente ayuda a determinar qué bordes agregar a un MST, pero no veo cómo lo logra. Mi comprensión de la propiedad de corte hasta el momento es que divide un MST en dos subconjuntos arbitrarios. ¿Alguna ayuda aquí? ¡Gracias!

Answer 1

Un corte de un gráfico conectado es un conjunto mínimo de bordes cuya eliminación separa el gráfico en dos componentes (piezas). La propiedad de corte mínimo dice que si uno de los bordes del corte tiene un peso menor que cualquier otro borde en el corte, entonces está en el MST. Para ver esto, suponga que hay un MST que no contiene el borde. Si agregamos el borde al MST obtenemos un ciclo que cruza el corte al menos dos veces, por lo que podemos romper el ciclo eliminando el otro borde del MST, creando así un nuevo árbol con menor peso, lo que contradice la minimización de la MST.