Теорема о раскраске дорог
В теории графов теорема раскраске дорог о , известная ранее как о раскраске дорог гипотеза , имеет дело с синхронизированными инструкциями . Вопрос заключается в том, можно ли, используя такие инструкции, достичь или определить местонахождение объекта или пункта назначения из любой другой точки сети (которая может представлять собой городские улицы или лабиринт ). [1] В реальном мире это было бы похоже на то, как если бы вы позвонили другу и спросили, как добраться до его дома, и он дал вам набор указаний, которые сработали бы независимо от того, откуда вы начали. Эта теорема также имеет значение в символической динамике .
Теорема была впервые выдвинута Роем Адлером и Бенджамином Вайсом . [2] Это доказал Авраам Трахтман . [3]
Пример и интуиция
[ редактировать ]
На изображении справа показан ориентированный граф с восемью вершинами , в котором каждая вершина имеет исходящую степень 2. (Каждая вершина в этом случае также имеет входную степень 2, но это не обязательно для существования синхронизирующей раскраски.) Ребра этого графика раскрашены в красный и синий цвета для создания синхронизирующей раскраски.
Например, рассмотрим вершину, отмеченную желтым цветом. Независимо от того, где вы начинаете граф, если вы пройдете все девять ребер в обходе «синий-красный-красный — синий-красный-красный — синий-красный-красный», вы окажетесь в желтой вершине. Аналогично, если вы пройдете все девять ребер в обходе «синий-синий-красный — синий-синий-красный — синий-синий-красный», вы всегда окажетесь в вершине, отмеченной зеленым, независимо от того, где вы начали.
Теорема о раскраске дорог утверждает, что для определенной категории ориентированных графов всегда можно создать такую раскраску.
Математическое описание
[ редактировать ]Пусть G — конечный сильно связный ориентированный граф , все вершины которого имеют одинаковую исходящую степень k . Пусть A — алфавит, содержащий буквы 1, ..., k . Синхронизирующая раскраска (также известная как свертываемая раскраска ) в G — это маркировка ребер в G буквами из A такая, что (1) каждая вершина имеет ровно одно выходящее ребро с заданной меткой и (2) для каждой вершины v в графе существует слово w над A такое, что все пути в G, соответствующие w, заканчиваются в v .
Терминология синхронизирующей раскраски обусловлена связью этого понятия с понятием синхронизирующего слова в теории конечных автоматов .
Чтобы такая раскраска вообще существовала, необходимо , чтобы G была апериодической . [4] Теорема о раскраске дорог утверждает, что также достаточно для существования такой раскраски апериодичности. Таким образом, задачу окраски дорог можно кратко сформулировать так:
- Каждый конечный сильно связный апериодический граф равномерной исходящей степени имеет синхронизирующую раскраску.
Предыдущие частичные результаты
[ редактировать ]Предыдущие результаты частичных или особых случаев включают следующее:
- Если G — конечный сильно связный апериодический ориентированный граф без кратных ребер и G содержит простой цикл простой длины , который является собственным подмножеством G , то G имеет синхронизирующую раскраску. [5]
- Если G — конечный сильно связный апериодический ориентированный граф (допускается несколько ребер) и каждая вершина имеет одинаковую входную и выходную степень k , то G имеет синхронизирующую раскраску. [6]
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Зайгел-Ицкович, Джуди (8 февраля 2008 г.). «Русский иммигрант решает математическую головоломку» . «Джерузалем Пост» . Проверено 13 сентября 2010 г.
- ^ Адлер и Вайс 1970 .
- ^ Трахтман 2009 .
- ^ Хегде и Джайн 2005 .
- ^ О'Брайен 1981 .
- ^ Приложение 2003 г.
Ссылки
[ редактировать ]- Адлер, Рой Л .; Вайс, Бенджамин (1970), Подобие автоморфизмов тора , Мемуары Американского математического общества , том. 98, дои : 10.1090/memo/0098 .
- Хегде, Раджниш; Джайн, Камаль (2005), «Теорема о мин-максе о гипотезе о раскраске дорог», Proc. EuroComb 2005 (PDF) , Дискретная математика и теоретическая информатика, стр. 279–284 .
- Кари, Яркко (2003), «Синхронизация конечных автоматов на эйлеровых орграфах», Theoretical Computer Science , 295 (1–3): 223–232, doi : 10.1016/S0304-3975(02)00405-X .
- О'Брайен, Г.Л. (1981), «Проблема раскраски дорог», Израильский математический журнал , 39 (1–2): 145–154, doi : 10.1007/BF02762860 .
- Трахтман, Авраам Н. (2009), «Проблема раскраски дорог», Израильский математический журнал , 172 (1): 51–60, arXiv : 0709.0099 , doi : 10.1007/s11856-009-0062-5 .