Partición de gráfico de cardinalidad mínima que elimina bordes específicos
Tengo un problema computacional que quiero resolver. No estoy seguro si ya se ha estudiado en literatura, o si es así con qué nombre. Agradecería cualquier indicación de literatura o sugerencias para un algoritmo.
Entrada: un gráfico conectado no dirigido G = (V, E) en el que ciertos bordes están etiquetados como "malos".
Salida: La partición de cardinalidad mínima de V tal que 1) todos los subgráficos inducidos de la partición están conectados y 2) ninguno de los subgráficos inducidos contiene un borde defectuoso.
¡Gracias!
Respuestas
Trate de ver lo que sucede cuando todos los bordes son malos .
¿Cuál sería la pregunta si yo preguntara:
¿Puede dividir el gráfico en tres particiones, por ejemplo , rojo, verde, azul , de modo que para cada borde, el "color" de los extremos de cada borde sea "cromático"?
(También hagamos que el gráfico sea un gráfico completo agregando bordes "buenos" entre todos los vértices no adyacentes).