Решена задача о раскраске дорог

Гипотеза о раскраске дорог (Road Coloring) была сформулирована в 1970 г. израильскими математиками Адлером и Вейссом в статье "Similarity of automorphisms of the torus". Гипотеза ставит вопрос о возможности синхронизации движения в конечном сильно связном графе с постоянной полустепенью исхода (постоянным числом ребер, исходящих из вершин).

Допустим, что это число равно двум, и каждое ребро имеет одну из двух характеристик, например, "окрашено" в красный или синий ("к" или "с") цвета. Из каждой вершины исходят одно "к" и одно "с" ребро, а длины циклов имеют общий делитель 1. Авторы гипотезы задают вопрос: всегда ли существует последовательность букв "к" и "с", одновременно (за равное количество шагов) приводящая к определенной вершине графа из любой другой вершины?

Аврааму Трахтману (Avraham Trahtman), бывшему жителю России и выпускнику Уральского государственного университета, а ныне профессору Университета Бар-Илан, удалось найти решение этой задачи. Его работа под названием "The road coloring problem" опубликована на сайте электронной библиотеки Корнельского университета arxiv.org.

Найденное Авраамом Трахтманом решение имеет важное значение в теории автоматов, так как указанную последовательность букв можно рассматривать в качестве команды для абстрактной вычислительной машины. Выполняя эту команду, машина имеет возможность вернуться в заданное время в определенное состояние после ошибочного действия.