Теорема о раскраске дорог
В теории графов теорема о раскраске дорог , ранее известная как гипотеза о раскраске дорог , имеет дело с синхронизированными инструкциями. Проблема заключается в том, можно ли с помощью таких инструкций достичь или найти объект или место назначения из любой другой точки в сети (которая может быть представлением городских улиц или лабиринта ). [1] В реальном мире это было бы похоже на то, как если бы вы позвонили другу, чтобы спросить дорогу к его дому, и он дал бы вам набор указаний, которые работали независимо от того, откуда вы начали. Эта теорема также применима к символической динамике .
Теорема была впервые выдвинута Роем Адлером и Бенджамином Вайсом ( 1970 ). Это доказал Авраам Трахтман ( 2009 ).
На изображении справа показан ориентированный граф из восьми вершин , в котором каждая вершина имеет исходящую степень 2. (Каждая вершина в этом случае также имеет входную степень 2, но это не обязательно для существования синхронизирующей раскраски.) Ребра этого графика были окрашены в красный и синий цвета, чтобы создать синхронизирующую окраску.
Например, рассмотрим вершину, отмеченную желтым цветом. Независимо от того, с какой точки графа вы начинаете, если вы пройдете все девять ребер в обходе «сине-красно-красно — сине-красно-красно — сине-красно-красно», вы окажетесь в желтой вершине. Точно так же, если вы пройдете все девять ребер в обходе «синий-синий-красный-синий-синий-красный-синий-синий-красный», вы всегда окажетесь в вершине, отмеченной зеленым, независимо от того, где вы начали.
Теорема о раскраске дорог утверждает, что для определенной категории ориентированных графов всегда можно создать такую раскраску.
Пусть G — конечный сильносвязный ориентированный граф , все вершины которого имеют одинаковую степень исхода k . Пусть А — алфавит, содержащий буквы 1, ..., к . Синхронизирующая раскраска (также известная как складная раскраска ) в G — это пометка ребер в G буквами из A такая, что (1) каждая вершина имеет ровно одно исходящее ребро с заданной меткой и (2) для каждой вершины v в графе существует слово w над A такое, что все пути в Gсоответствующие w заканчиваются на v .
