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

== Описание метода ==

Метод цветового кодирования является рандомизированным. Вершины графа G = (V, E), в котором ищется изоформный подграф <math>H = (V_H, E_H)</math>, случайным образом раскрашиваются при помощи <math>k = |V_H|</math> цветов. Если <math>|V_H| = O(log \; |V|)</math>, то с небольшой вероятностью, но лишь полиномиально небольшой (т. е. чуть выше полиномиальной) все вершины подграфа G, изоморфного H, если такой подграф существует, будут раскрашены в разные цвета. Такой подграф называется ''цветокодированным''. Метод цветового кодирования использует то обстоятельство, что во многих случаях проще выявить цветокодированные подграфы, чем нераскрашенные.

Возможно, простейший интересный частный случай проблемы изоморфизма подграфов выглядит следующим образом. Пусть даны ориентированный или неориентированный граф G = (V, E) и число k. Содержит ли граф G простой (ориентированный) путь длины k? Содержит ли граф G простой (ориентированный) цикл, длина которого ''в точности'' равна k? Далее будет описан алгоритм с временем выполнения <math>2^{O(k)} \cdot |E|</math>, который принимает на вход граф G = (V, E), функцию раскраски <math>c: V \to \{ 1, ..., k \}</math> и вершину <math>s \in V</math> и находит раскрашенный путь длины k – 1, начинающийся в вершине s, если таковой существует. Для поиска раскрашенного пути длины k – 1 в графе G, начинающегося в произвольной вершине, можно добавить к V новую вершину s', раскрасить ее в новый цвет 0 и соединить ребрами со всеми вершинами V, после чего выполнить поиск раскрашенного пути длины k, начинающегося в s'.