Теорема о раскраске дорог

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

ФормулировкаПравить

Пусть G — конечный сильно связанный ориентированный граф, в котором все вершины имеют одинаковую полустепень исхода k. Пусть A — алфавит, содержащий буквы 1, …, k. Синхронизирующая раскраска (известная также как разборная раскраска) графа G — это разметка рёбер графа G буквами из A, такая что (1) каждая вершина имеет ровно одно исходящее ребро с указанной меткой, и (2) для каждой вершины v в графе существует слово w над A, такое что все пути в G, соответствующие w, завершаются в v.

Термин синхронизирующая раскраска возник в связи со связью с термином синхронизирующее слово в теории конечных автоматов.

Для того, чтобы раскраска существовала, необходимо, чтобы G был апериодичным; то есть длины всевозможных циклов в графе должны быть взаимно просты. Теорема о раскраске дорог утверждает, что апериодичность является также достаточным для существования раскраски. Таким образом, задачу о раскраске дорог можно сформулировать коротко следующим образом:

Любой конечный сильно связанный апериодичный ориентированный граф с постоянной полустепенью исхода имеет синхронизирующую раскраску.

ПримерПравить

 

Ориентированный граф с синхронизирующей раскраской

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

Например, рассмотрим выкрашенную в жёлтый цвет вершину. Неважно откуда вы начнёте, но если вы пойдёте по правилу «синий — красный — красный — синий — красный — красный — синий — красный — красный», вы завершите свой путь в жёлтой вершине. Похожим образом, если вы будете идти придерживаясь последовательности «синий — синий — красный — синий — синий — красный — синий — синий — красный», вы всегда завершите свой путь в зелёной вершине.

Теорема о раскраске дорог утверждает, что для некоторой категории ориентированных графов такой вид раскраски существует всегда.

ИсторияПравить

Гипотеза была выдвинута Роем Адлером^[en] и Бенджамином Вайсом^[en] и доказана Абрамом Трахтманом.

Частичные результаты или специальные случаи, полученные до доказательства теоремы:

• Если G — конечный сильно связанный апериодичный ориентированный граф без кратных рёбер и G содержит цикл простой длины, тогда G имеет синхронизирующую раскраску.
• Если G — конечный сильно связанный апериодичный ориентированный граф (кратные рёбра разрешены), и все вершины имеют одну и ту же полустепень захода и исхода k, тогда G имеет синхронизирующую раскраску.

См. такжеПравить

• Проблема четырёх красок
• Раскраска графов

ЛитератураПравить

• R. L. Adler, B. Weiss. Similarity of automorphisms of the torus. — 1970. — Т. 98.
• Rajneesh Hegde, Kamal Jain. Proc. EuroComb 2005. — 2005. — С. 279—284. — (Discrete Mathematics & Theoretical Computer Science).
• Jarkko Kari. Synchronizing finite automata on Eulerian digraphs // Theoretical Computer Science. — 2003. — Т. 295, вып. 1—3. — С. 223—232. — doi:10.1016/S0304-3975(02)00405-X.
• G. L. O'Brien. The road-colouring problem // Israel Journal of Mathematics. — 1981. — Т. 39, вып. 1—2. — С. 145—154. — doi:10.1007/BF02762860.
• Avraham N. Trahtman. The road coloring problem // Israel Journal of Mathematics. — 2009. — Т. 172, вып. 1. — С. 51—60. — doi:10.1007/s11856-009-0062-5. — arXiv:0709.0099.