Dejemos que $G = (V, E)$ sea un grafo conexo que tiene un la combinación perfecta . Diseñar (y demostrar su exactitud) un $O(|V | + |E|)$ algoritmo de complejidad temporal que construye un árbol de expansión $T$ de $G$ tal que $V (T)$ admite una bipartición en dos conjuntos estables de cardinalidad máxima en $T$ .
Me encontré con este problema en un libro Tengo sobre la teoría de los gráficos, y ya he luchado durante un par de horas. El problema es que no tengo un punto de partida para ello. Cualquier tipo de ayuda se agradecería.
