«Синхронизирующая раскраска графов»
Синхронизирующая раскраска графа — это раскраска рёбер ориентированного графа в два цвета (красный и синий), такая что:
- из каждой вершины выходит ровно одно красное и ровно одно синее ребро
- для каждой вершины в графе можно составить инструкцию, как из любой вершины попасть в заданную, проходя по рёбрам нужного цвета
Инструкция ▼
- Выберите граф из списка
- Можете изменить раскраску, изменяя цвета рёбер (нажатием на ребро)
- Проверьте, является ли раскраска синхронизирующей
- Введите предполагаемое синхронизирующее слово
Для того, чтобы раскраска существовала, необходимо, чтобы длины всевозможных циклов в сильно связанном графе должны были взаимно просты. Теорема о раскраске дорог утверждает, что это условие является также достаточным для существования раскраски. Гипотеза была выдвинута Роем Адлером и Бенджамином Вайсом в 1970 году и доказана Абрамом Трахтманом в 2009 году.