Имеется задача: Может кто-нибудь разъяснить, что подразумевается под фразой "граф K-раскрашиваем..."? Речь идет о реберной раскраске?
Граф K-раскрашиваем, если существует K-раскраска такая, что никакие две вершины, соединенные ребром, не раскрашены одинаковыми цветами.
Т.е. задача сводится к тому чтобы, например, первую вершину красим в черный, всех ее соседей в белый, всех соседей-соседей в черный и т.д. Решить такое можно с помощью, например, BFS. Я Вас правильно понял?
Способ представления графа выбирается исходя из его структуры (в общем случае). Но для данной задачи удобен способ представления "список примыканий". Элементы списка ссылаются на список связанных вершин. Пусть изначально цвет всех вершин [x] - неопределённый, а по мере продвижения алгоритма по списку, он будет заполняться: [Ч]ёрный или [Б]елый. [1 [x]] -> [2 [x]], [3 [x]] [2 [x]] -> [1 [x]], [3 [x]], [4 [x]] [3 [x]] -> [1 [x]], [2 [x]], [5 [x]] [4 [x]] -> [2 [x]], [5 [x]] [5 [x]] -> [3 [x]], [4 [x]] Красиво будет сделать рекурсивную раскраску, но сложность надо будет просчитать - тут не факт, что рекурсия даст полиномическую сложность. Как только рекурсивная фунция обнаружит противоречие, вершина [Ч] закрашивается в [Б] или наоборот, то надо остановиться, если не обнаружит, то граф можно раскрасить в два цвета. Пример трассировки рекурсивной расскраски (данный граф имеет хроматическое число выше 2, то есть двумя цветами не раскрасить, но рекурсивная функция узнает об этом не сразу): [1 [Ч-1, Ч-5, Б-9]] -> [2 [Б-2]], [3 [x]] [2 [Б-3]] -> [1 [Ч-4]], [3 [Ч-6]], [4 [x]] [3 [Ч-7]] -> [1 [Б-8]], [2 [x]], [5 [x]] [4 [x]] -> [2 [x]], [5 [x]] [5 [x]] -> [3 [x]], [4 [x]] Будет 9 шагов раскраски, после шага Б-8 (8-й шаг, вершина 1 красится в белый), фунция пойдёт в вершину 1, и обнаружит, что та уже [Ч]ёрная, то есть 9-й шаг - последний (+ накладные расходы на выход из рекурсии). В целом эффективно, но вероятно, есть способ и побыстрее.
