В теории графов дорога раскраска теорема , известная ранее как дороги окраски гипотезой , имеет дело с синхронизированным инструкциями. Проблема заключается в том, можно ли с помощью таких инструкций достичь или определить местонахождение объекта или пункта назначения из любой другой точки в сети (которая может быть изображением городских улиц или лабиринта ). [1] В реальном мире это было бы так, как если бы вы позвонили другу, чтобы спросить дорогу к его дому, и он дал вам набор направлений, которые работают независимо от того, откуда вы начинаете. Эта теорема также имеет значение в символической динамике .
Теорема была впервые высказана Роем Адлером и Бенджамином Вейссом ( 1970 ). Это было доказано Авраамом Трахтманом ( 2009 ).
Пример и интуиция [ править ]
На изображении справа показан ориентированный граф с восемью вершинами, в котором каждая вершина имеет исходную степень 2. (Каждая вершина в этом случае также имеет внутреннюю степень 2, но это не обязательно для существования синхронизирующей раскраски). этого графика были окрашены в красный и синий цвета, чтобы создать синхронизирующую окраску.
Например, рассмотрим вершину, отмеченную желтым цветом. Независимо от того, где на графике вы начинаете, если вы пройдете все девять ребер по схеме «синий-красный-красный — синий-красный-красный — синий-красный-красный», вы окажетесь в желтой вершине. Точно так же, если вы пройдете все девять ребер в обходе «синий-синий-красный - синий-синий-красный - синий-синий-красный», вы всегда окажетесь в вершине, отмеченной зеленым цветом, независимо от того, с чего вы начали.
Теорема о раскраске дорог утверждает, что для определенной категории ориентированных графов всегда можно создать такую раскраску.
Математическое описание [ править ]
Пусть G конечная, сильно связным , ориентированный граф , в котором все вершины имеют один и тот же из-градусный K . Пусть A - алфавит, содержащий буквы 1, ..., k . Синхронизации окраска (также известная как складная окраска ) в G является маркировкой ребер в G с буквами от таким образом, что (1) каждой вершины имеет ровно одну исходящую кромку с заданной меткой и (2) для каждой вершины V в графа существует такое слово w над A , что все пути в Gсоответствующие w оканчиваются на v .
Терминология « синхронизирующая раскраска» связана с отношением между этим понятием и понятием синхронизирующего слова в теории конечных автоматов .
Чтобы такая раскраска вообще существовала, необходимо, чтобы G была апериодической . [2] Теорема о раскраске дорог утверждает, что апериодичность также достаточна для существования такой раскраски. Таким образом, проблему окраски дороги можно кратко сформулировать так:
- Каждый конечный сильно связный ориентированный апериодический граф равномерной исходящей степени имеет синхронизирующую раскраску.
Предыдущие частичные результаты [ править ]
Предыдущие частичные или особые результаты включают следующее:
- Если G является конечным сильно связана апериодическим ориентированным графом, без кратных ребер , а G содержит простой цикл из простой длины , который является подмножеством G , то G имеет синхронизирующую окраску. (О'Брайен, 1981)
- Если G - конечный сильно связный апериодический ориентированный граф (допускается наличие нескольких ребер) и каждая вершина имеет одинаковую входную и исходящую степень k , то G имеет синхронизирующую раскраску. (Кари, 2003)
См. Также [ править ]
Заметки [ править ]
- ^ Seigel-Ицкович, Judy (2008-02-08). «Русский иммигрант решает математические головоломки» . "Джерузалем пост" . Проверено 13 сентября 2010 .
- ^ Хедж & Jain (2005) .
Ссылки [ править ]
- Адлер, Р.Л .; Вайс Б. (1970), Подобие автоморфизмов тора , Мемуары Американского математического общества, 98..
- Хегде, Раджниш; Джейн, Камаль (2005), "Теорема о минимуме и максимуме о гипотезе о раскраске дорог", Proc. EuroComb 2005 (PDF) , Дискретная математика и теоретическая информатика, стр. 279–284.
- Kari, Яркко (2003), "Синхронизация конечных автоматов на эйлеровых орграфах", Теоретическая информатика , 295 (1-3): 223-232, DOI : 10.1016 / S0304-3975 (02) 00405-X.
- О'Брайен, GL (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.
