Раскраска графа в 3 цвета с использованием заданной функции

Question

У меня есть функция Three_colorability(n,E), которая выдает true (когда граф с этими ребрами и вершинами можно раскрасить тремя цветами) или false (если нет).(! Нет параметра, чтобы знать, что уже окрашен), мы предполагаем, что эта функция работает в сложности линейной времени.

Мне нужно составить алгоритм 3-раскраски данного неориентированного графа G с использованием заданной функции, который будет работать за полиномиальное время.

Я не могу прийти к решению этой проблемы.

Answer 1

Добавьте 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.

Чтобы найти цвет для всех вершин, постепенно найдите цвет вершин и добавьте эти два ребра в граф.