Русская Википедия:Теорема о раскраске дорог
В теории графов теорема о раскраске дорог, известная до недавнего времени как гипотеза о раскраске дорог, имеет дело с инструкциями синхронизации. Задача ставится в нахождении таких инструкций, чтобы независимо от начального положения объекта можно было бы дойти до пункта назначения в сети (которая может представлять собой улицы города или лабиринт)[1]. В реальном мире можно данную задачу представить как набор инструкций для вашего друга, по которым он может добраться до вашего дома независимо от того, где он находится сейчас. Теорема также имеет приложение в символической динамике.
Формулировка
Пусть G — конечный сильно связанный ориентированный граф, в котором все вершины имеют одинаковую полустепень исхода k. Пусть A — алфавит, содержащий буквы 1, …, k. Синхронизирующая раскраска (известная также как разборная раскраска) графа G — это разметка рёбер графа G буквами из A, такая что (1) каждая вершина имеет ровно одно исходящее ребро с указанной меткой, и (2) для каждой вершины v в графе существует слово w над A, такое что все пути в G, соответствующие w, завершаются в v.
Термин синхронизирующая раскраска возник в связи со связью с термином синхронизирующее слово в теории конечных автоматов.
Для того, чтобы раскраска существовала, необходимо, чтобы G был апериодичнымШаблон:Sfn; то есть длины всевозможных циклов в графе должны быть взаимно просты. Теорема о раскраске дорог утверждает, что апериодичность является также достаточным для существования раскраски. Таким образом, задачу о раскраске дорог можно сформулировать коротко следующим образом:
- Любой конечный сильно связанный апериодичный ориентированный граф с постоянной полустепенью исхода имеет синхронизирующую раскраску.
Пример
Рисунок показывает ориентированный граф с восемью вершинами, в котором каждая вершина имеет полустепень исхода 2 (в данном графе каждая вершина имеет полустепень захода также равную 2, но это не обязательно, чтобы синхронизирующая раскраска существовала). Рёбра графа выкрашены в красный и синий цвета для образования синхронизирующей раскраски.
Например, рассмотрим выкрашенную в жёлтый цвет вершину. Неважно откуда вы начнёте, но если вы пойдёте по правилу «синий — красный — красный — синий — красный — красный — синий — красный — красный», вы завершите свой путь в жёлтой вершине. Похожим образом, если вы будете идти придерживаясь последовательности «синий — синий — красный — синий — синий — красный — синий — синий — красный», вы всегда завершите свой путь в зелёной вершине.
Теорема о раскраске дорог утверждает, что для некоторой категории ориентированных графов такой вид раскраски существует всегда.
История
Гипотеза была выдвинута Шаблон:Iw и Шаблон:IwШаблон:Sfn и доказана Абрамом ТрахтманомШаблон:Sfn.
Частичные результаты или специальные случаи, полученные до доказательства теоремы:
- Если G — конечный сильно связанный апериодичный ориентированный граф без кратных рёбер и G содержит цикл простой длины, тогда G имеет синхронизирующую раскраскуШаблон:Sfn.
- Если G — конечный сильно связанный апериодичный ориентированный граф (кратные рёбра разрешены), и все вершины имеют одну и ту же полустепень захода и исхода k, тогда G имеет синхронизирующую раскраскуШаблон:Sfn.
См. также
Примечания
Литература
