Цветовое кодирование — , полезная для обнаружения . Может быть использована, к примеру, для обнаружения простого пути длины в заданном графе. Традиционный алгоритм цветового кодирования является вероятностным, но решение может быть без существенного увеличения времени работы.

Цветовое кодирование также применяется для обнаружения циклов заданной длины и в более общем случае, как в задаче поиска изоморфного подграфа (NP-полная задача), где оно даёт алгоритмы полиномиального времени, если искомый подграф имеет ограниченную древовидной шириной.

Эта техника широко используется в различных областях, включая науку, инженерию, медицину и информатику, для облегчения восприятия и анализа сложной информации.

Метод цветового кодирования предложили и анализировали в 1994 году. Авторы - Нога Алон, Рафаэль Юстер и Юрий Цвик.

Результаты Следующие результаты могут быть получены методом цветового кодирования:

Для любой константы , если граф содержит цикл размера , такой цикл может быть найден за: среднее время, или худшее время, где является экспонентой умножения матрицСм. Алгоритм Копперсмита — Винограда. Экспонента умножения матриц — это степень размера матрицы асимптотической сложности алгоритма умножения матриц.. Для любой константы и любого графа из нетривиального семейства графов, замкнутого по минорам (например, планарные графы), если содержит простой цикл размера , то такой цикл может быть найден за: среднее время, или за время в худшем случае. Если граф содержит подграф, изоморфный графу ограниченной древовидной ширины, который имеет вершин, то такой подграф может быть найден за полиномиальное время.

Метод Чтобы решить задачу нахождения подграфа в данном графе , где может быть путём, циклом или любым графом с ограниченной древовидной шириной, а , метод цветового кодирования начинает со случайной раскраски каждой вершины в с помощью цветов, а потом пытается найти полноцветную копию в раскрашенном . Здесь под полноцветным графом понимается граф, в котором каждая вершина раскрашена в свой цвет. Метод работает путём повторения (1) случайной раскраски графа и (2) нахождения полноцветной копии целевого подграфа. В конечном счёте целевой подграф может быть найден, если процесс повторять достаточное число раз.

Предположим, что копия в становится полноцветной с некоторой ненулевой вероятностью . Отсюда следует, что при повторении случайной раскраски раз эта копия однажды встретится. Заметим, что даже когда вероятность мала, известно, что при вероятность лишь полиномиально мала. Предположим, что существует алгоритм, который для данного графа и раскраски, которая отображает каждую вершину в один из цветов, находит копию полноцветной копии , если она существует, за некоторое время . Тогда ожидаемое время поиска копии в , если она существует, равно .

Иногда желательно использовать более жёсткую версию цветной раскраски. Например, в контексте поиска циклов в планарных графах можно разрабатывать алгоритм для поиска хорошо раскрашенных циклов. Здесь под хорошо раскрашенным циклом понимается раскраска последовательными цветами.

Пример В качестве примера возьмём поиск простого цикла длины в графе .

При применении метода случайной раскраски каждый простой цикл имеет вероятность стать полноцветным, поскольку имеется способов выкрасить вершин цикла, среди которых встречается вариантов полноцветной раскраски. Тогда алгоритм (описан ниже) может быть использован для поиска полноцветных циклов в случайно раскрашенном графе за время , где является константой умножения матриц. Тогда требуется полное время для нахождения простого цикла длины в .

Алгоритм поиска полноцветного цикла сначала находит все пары вершин в , соединённые простым путём длины , а потом проверяет, соединены ли две вершины в каждой паре. Если задана функция раскраски для графа , перенумеруем все разбиения множества цветов на два подмножества размера примерно в каждом. Для каждого такого разбиения пусть будет множеством вершинам, выкрашенных цветами из , а будет множеством вершин, выкрашенных цветами из . Пусть и обозначают подграфы, порожденные и соответственно. Рекурсивно находим полноцветные пути длины в и . Представим, что булевы матрицы и представляют связь каждой пары вершин в и полноцветным путём соответственно, и пусть будет матрицей, описывающей смежность вершин и , тогда булево произведение даёт все пары вершин в , соединённые полноцветным путём длины . Объединение матриц, полученных на всех разбиениях множества цветов, даёт , что приводит ко времени работы . Хотя этот алгоритм находит только конечные точки полноцветного пути, может быть использован другой алгоритм Алона и Наора, который и находит, собственно, полноцветный путь.

Дерандомизация цветового кодирования вовлекает перечисление возможных раскрашиваний графа так, что рандомизация раскраски больше не нужна. Для обнаружения целевого подграфа в , перечисление должно включать, по меньшей мере, один случай, где полноцветн. Чтобы это получить, достаточно перечислить -совершенное семейство хеш-функций из в . По определению, функция -совершенна, если для любого подмножества множества , где , существует хеш-функция из , такая что является . Другими словами, должна существовать хеш-функци в , которая раскрашивает заданные вершин в различных цвета.

Имеется несколько подходов к построению такого -идеального семейства хеша:

Лучшее явное построение предложили Мони Наор, Леонард Дж. Шульман и Аравинд Сринивасан, в котором можно получить семейство размера . Это построение не требует, чтобы целевой подграф содержался в исходной задаче нахождения подграфа. Другое явное построение предложили Джанетта П. Шмидт и Алан Сигель даёт семейство размера . Ещё одно построение, которое появилось в исходной статье Нога Алона и др., можно получить сначала путём построения -совершенного семейства, которое отображает в , с построением другого -совершенного семейства, которое отображает в . На первом шаге можно построить такое семейство с случайными битами, которое почти -независимо, и пространство, необходимое для генерации этих случайных бит, может быть ограничено величиной . На втором шаге, как показали Джанетта П. Шмидт и Алан Зигель , размер такого -идеального семейства может быть . Следовательно, составляя -идеальные семейства из обоих шагов, можно получить -совершенное семейство размера , которое отображает из в .

В случае дерандомизации идеального раскрашивания, когда каждая вершина подграфа раскрашивается последовательно, требуется -идеальное семейство хэш-функций из в . Достаточное -совершенное семейство, отображающее из в , может быть построено способом, подобным подходу 3 выше (первый шаг). В частности, это делается использованием случайных бит, которые почти независимы, а размер получающегося -совершенного семейства будет равен .

Дерандомизация метода цветового кодирования может быть легко распараллелена, что приводит к эффективным алгоритмам в классе NC.

Приложения Недавно цветовое кодирование привлекло внимание ученых из области биоинформатики. Пример — определение сигнальных путей в сетях белок-белкового взаимодействия (ББВ). Другим примером является обнаружение и подсчёт числа в сетях ББВ. При изучении как сигнальных путей, так и позволяет более глубокое понимание похожести разницы многих биологических функций, процессов и структур в организмах.

Вследствие большого числа генетических данных, которые можно собрать, поиск путей или мотивов может занимать продолжительное время. Однако, используя метод цветового кодирования, мотивы и сигнальные пути с вершинами в сети с вершинами могут быть найдены очень эффективно за полиномиальное время. Это позволяет исследовать более сложные или больших размеров структуры в сетях ББВ.

Примечания

Литература

Литература для дальнейшего чтения

Категория:Алгоритмы на графах