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

Израильскому математику удалось обосновать гипотезу о раскраске дорог (Road Coloring), имеющую важное значение в теории автоматов.

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

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

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

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

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