4551
правка
Цветовое кодирование: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 19: | Строка 19: | ||
== Основные результаты == | == Основные результаты == | ||
Лемма 1. Пусть G = (V, E) – ориентированный или неориентированный граф, а c V !f {1; ; kg – раскраска его вершин при помощи k цветов. Цветной путь длины k - 1 в графе G, если такой существует, может быть найден за время 2O( ■ \E\ в наихудшем случае. | |||
Лемма 2. Пусть G = (V, E) – ориентированный или неориентированный граф, а c V !f {1; ; kg – раскраска его вершин при помощи k цветов. Все пары вершин, соединенные цветными путями длины k - 1 в G, могут быть найдены за время 2O(k) • \V\\E\ или 2o(k) Vj! в наихудшем случае (здесь ! < 2:376 обозначает показатель степени при умножении матриц). | |||
На основе вышеприведенных лемм мыли получены следующие результаты. | |||
Теорема 3. Простой ориентированный или неориентированный путь длины k - 1 в (ориентированном или неориентированном) графе G = (V, E), содержащем такой путь, может быть найден за ожидаемое время 2O( ■ \V\ в случае неориентированного графа и за ожидаемое время 2°^). Ej в случае ориентированного графа. | |||
Теорема 4. Простой ориентированный или неориентированный цикл размера k в (ориентированном или неориентированном) графе G = (V, E), содержащем такой цикл, может быть найден за ожидаемое время 2O( ■ \V\ либо \V\<°. | |||
Цикл длины k в замкнутых относительно операции взятия минора семействах графов может быть найден при помощи цветового кодирования еще быстрее (для планарных графов чуть более быстрый алгоритм приведен в [6]). | |||
Теорема 5. Пусть C – нетривиальное семейство графов, замкнутых относительно операции взятия минора, а k > 3 – фиксированное целое число. Тогда существует рандомизированный алгоритм, который для заданного графа G = (V, E) из семейства C находит Q (простой цикл размера k) в G, если таковой существует, за ожидаемое время O(|V|). | |||
Как упоминалось выше, все эти теоремы могут быть дерандомизированы с коэффициентом log |V|. Кроме того, эти алгоритмы легко могут быть распараллелены. | |||
== Применение == | |||
