|
Для начала выдели связные компоненты графы и раскрашивай каждый из них по отдельности. Число цветов, наверное разумнее будет находить двоичным поиском - в худшем случае он лишь ненамного замедлит программу, но зато свободы в придумывании эвристик будет гораздо больше.
На каждом шаге двоичного поиска перед тобой будет стоять задача - можно ли раскрасить данный связный граф K цветами. Решай перебором - выбери нераскрашенную вершину, перебери цвет для нее, отличный от цветов смежных с ней уже-раскрашенных вершин, рекурсивно попытайся раскрасить оставшиеся вершины, если не получилось - откат, пробуй другой цвет. Выбирать вершину можно по разному, например можно взять ту, с которой связано наибольшее число нераскрашенных вершин. Или ту, для которой число цветов в которую ее можно раскрасить на данном шаге наименьшее. Если это число = 0 (т.е. ее соседи уже покрашены во все K цветов), можно прекратить перебор на этом шаге. Придумывай эвристики для своих конкретных графов чтобы сократить перебор, т.к. в общем случае задача NP-сложная и требует экспоненциального времени.
|
Линейный вид
