Разбиение графа минимальной мощности, удаляющее определенные ребра

Question

У меня есть вычислительная проблема, которую я хочу решить. Я не уверен, изучалось ли это уже в литературе, и если да, то под каким названием. Буду признателен за любые указатели на литературу или предложения по алгоритму.

Вход: связный неориентированный граф G = (V, E), в котором некоторые ребра помечены как «плохие».

Выход: минимальная мощность разбиения V такое, что 1) все индуцированные подграфы разбиения связаны и 2) ни один из индуцированных подграфов не содержит плохих ребер.

Спасибо!

Answer 1

Попробуйте посмотреть, что происходит, когда все края плохие .

Какой был бы вопрос, если бы я спросил:

Можете ли вы разделить граф на три части , например красный, зеленый, синий , чтобы для каждого ребра «цвет» конечных точек каждого ребра был «хроматическим».

(Давайте также превратим граф в полный граф, добавив «хорошие» ребра между всеми несмежными вершинами.)