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

'''Лемма 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> обозначает показатель степени при умножении матриц).