4551
правка
Цветовое кодирование: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 19: | Строка 19: | ||
== Основные результаты == | == Основные результаты == | ||
Лемма 1. Пусть G = (V, E) – ориентированный или неориентированный граф, а c V | '''Лемма 1'''. Пусть G = (V, E) – ориентированный или неориентированный граф, а <math>c: V \to \{ 1, ..., k \}</math> – раскраска его вершин при помощи k цветов. Цветной путь длины k - 1 в графе G, если такой существует, может быть найден за время <math>2^{O(k)} \cdot |E|</math> в наихудшем случае. | ||
'''Лемма 2'''. Пусть G = (V, E) – ориентированный или неориентированный граф, а <math>c: V \to \{ 1, ..., k \}</math> – раскраска его вершин при помощи k цветов. Все пары вершин, соединенные цветными путями длины k - 1 в G, могут быть найдены за время <math>2^{O(k)} \cdot |V| |E|</math> или <math>2^{O(k)} \cdot |V|^{\omega}</math> в наихудшем случае (здесь <math>\omega < 2.376</math> обозначает показатель степени при умножении матриц). | |||
Теорема 4. Простой ориентированный или неориентированный цикл размера k в (ориентированном или неориентированном) графе G = (V, E), содержащем такой цикл, может быть найден за ожидаемое время | На основе вышеприведенных лемм были получены следующие результаты. | ||
'''Теорема 3. Простой ориентированный или неориентированный путь длины k - 1 в (ориентированном или неориентированном) графе G = (V, E), содержащем такой путь, может быть найден за ожидаемое время <math>2^{O(k)} \cdot |V|</math> в случае неориентированного графа и за ожидаемое время <math>2^{O(k)} \cdot |E|</math> в случае ориентированного графа.''' | |||
'''Теорема 4. Простой ориентированный или неориентированный цикл размера k в (ориентированном или неориентированном) графе G = (V, E), содержащем такой цикл, может быть найден за ожидаемое время <math>2^{O(k)} \cdot |V| |E|</math> либо <math>2^{O(k)} \cdot |V|^{\omega}</math>.''' | |||
Цикл длины k в замкнутых относительно операции взятия минора семействах графов может быть найден при помощи цветового кодирования еще быстрее (для планарных графов чуть более быстрый алгоритм приведен в [6]). | Цикл длины k в замкнутых относительно операции взятия минора семействах графов может быть найден при помощи цветового кодирования еще быстрее (для планарных графов чуть более быстрый алгоритм приведен в [6]). | ||
Теорема 5. Пусть C – нетривиальное семейство графов, замкнутых относительно операции взятия минора, а k > | |||
'''Теорема 5. Пусть C – нетривиальное семейство графов, замкнутых относительно операции взятия минора, а <math>k \ge 3</math> – фиксированное целое число. Тогда существует рандомизированный алгоритм, который для заданного графа G = (V, E) из семейства C находит <math>C_k</math> (простой цикл размера k) в G, если таковой существует, за ожидаемое время O(|V|).''' | |||
Как упоминалось выше, все эти теоремы могут быть дерандомизированы с коэффициентом log |V|. Кроме того, эти алгоритмы легко могут быть распараллелены. | Как упоминалось выше, все эти теоремы могут быть дерандомизированы с коэффициентом log |V|. Кроме того, эти алгоритмы легко могут быть распараллелены. | ||
== Применение == | == Применение == | ||
