У меня есть функция three_colorability(n,E), которая дает вывод true (когда граф с этими ребрами и вершинами может быть окрашен в 3 цвета) или false (если нет). (! нет параметра, чтобы узнать, что уже было окрашено) Мы предполагаем, что эта функция работает в линейной временной сложности.
Мне нужно составить алгоритм 3-раскраски заданного неориентированного графа G с использованием заданной функции, который будет работать за полиномиальное время.
Я не могу прийти к решению этого.
Добавьте 3 новых узла с именами C1, C2 и C3 по цвету, который они представляют. Добавьте ребра между новыми узлами (C1,C2), (C2,C3) и (C1,C3). Если three_colorability(V,E) верно, то three_colorability(V+{C1,C2,C3},E+{(C1,C2),(C2,C3),(C1,C3)}) также верно.
Для каждой (исходной) вершины v функция three_colorability() возвращает true хотя бы для одного из графов с добавленными двумя ребрами {(v,C1), (v,C2), (v,C3)}. Например. если three_colorability() возвращает true для графа с добавленными ребрами {(v,C2), (v,C3)}, это означает, что v можно окрасить в цвет 1.
Чтобы найти цвет для всех вершин, постепенно найдите цвет вершины и добавьте эти 2 ребра в граф.
