4551
правка
Цветовое кодирование: различия между версиями
Перейти к навигации
Перейти к поиску
→Описание метода
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
Метод цветового кодирования является рандомизированным. Вершины графа 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), в котором ищется изоформный подграф <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? Далее будет описан алгоритм с временем выполнения | Возможно, простейший интересный частный случай проблемы изоморфизма подграфов выглядит следующим образом. Пусть даны ориентированный или неориентированный граф 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'. | ||