Algoritmo de partición del árbol de expansión mínima

Question

Se pueden encontrar muchos MST al dividir un grafo, encontrar el MST de cada "mitad" y luego conectar las dos mitades de la forma menos costosa.

Me pidieron que proporcionara un contraejemplo para refutar este algoritmo. Esto es lo que se me ocurrió:

Pensé, bueno, esto no se puede dividir vertical u horizontalmente para que funcione el algoritmo, pero luego me di cuenta de que se podría dividir verticalmente a lo largo de la caja más a la izquierda para que funcione el algoritmo de partición. Intenté pensar en algunos otros polígonos para usar como ejemplos, pero siempre me topaba con el mismo problema. También le pregunté a un amigo en clase y él tampoco pudo encontrar nada.

¿Existe un grafo que desapruebe completamente este algoritmo, de tal manera que no se pueda hacer ninguna partición para encontrar con éxito el MST? Si es así, ¿cuál es un ejemplo?

Answer 1

Dado un árbol de expansión mínimo, seguramente siempre se puede encontrar una buena partición post facto escogiendo una arista del árbol de expansión y particionando en los conjuntos de vértices de los dos subárboles obtenidos eliminando esa arista. Por supuesto, si no conocemos el árbol de expansión de antemano, esto no es muy práctico, pero sugiere la necesidad de ser más específico sobre el algoritmo que estás tratando de vencer, porque necesitas explotar algo específico sobre cómo el algoritmo encuentra una partición. (Alternativamente, el punto podría ser simplemente que no todas las particiones funcionan, en cuyo caso basta con encontrar una partición que no dé un MST en todo el grafo, como hiciste en tu ejemplo.)