Цветовое кодирование: различия между версиями

Цветной путь длины k - 1, начинающийся в некоторой конкретной вершине s, вычисляется при помощи методов динамического программирования. Предположим, что для каждой вершины <math>v \in V</math> задано множество возможных цветов для цветных путей длины i, соединяющих s и v. Заметим, что нет необходимости записывать все цветные пути, соединяющие s и v. Вместо этого запишем все множества цветов, появляющихся на этих путях. Для каждой вершины v существует набор из не более чем <math>\binom{k}{i}</math> множеств цветов. Теперь проверим каждое подмножество C, принадлежащее к набору v, и каждое ребро <math>(v, u) \in E</math>. Если <math>c(u) \notin C</math>, добавим множество <math>C \cup \{ c(u) \}</math> к набору u, соответствующему цветным путям длины i + 1. Граф G содержит цветной путь длины k - 1 с раскраской ''c'' в том и только том случае, если окончательная коллекция, соответствующая путям длины k - 1, непуста по крайней мере для одной вершины. Количество операций, выполненных схематично описанным выше алгоритмом, не превышает <math>O \Bigl( \sum_{i = 0}^k i \binom{k}{i} \cdot |E| \Bigr)</math>, что, очевидно, составляет <math>O(k \; 2^k \cdot |E|)</math>

Полученные алгоритмы, использующие метод цветового кодирования, можно дерандомизировать с небольшой потерей эффективности. Все, что требуется для дерандомизации – это семейство раскрасок графа G = (V, E), такое, что каждому подмножеству k вершин G по крайней мере одна из этих раскрасок назначает разные цвета. Такое семейство также называется семейством ''идеальных функций хеширования'' от {1, 2, ..., |V|} до {1, 2, ..., k}. Подобное семейство строится явным образом при помощи сочетания методов из работ [1, 9, 12, 16]. Технику дерандомизации, обеспечивающую улучшение с постоянным коэффициентом, см. в работе [5].