在上面的有向图中，选择任意顶点并按蓝-红-红的顺序沿着箭头走三次。您将始终到达绿色顶点。 类似地，按蓝-蓝-红的顺序走三次，无论您从哪里开始，都将始终到达黄色顶点。 这被称为同步着色。
道路着色问题是同步着色一个有向有限强连通图的问题，该图具有相同的出度，并且所有环长度的最大公约数为 1。 Trahtman (2007) 提供了这个问题的肯定解。
道路着色问题
另请参阅
有向图, 图, 旅行商问题使用 探索
参考文献
Adler, R. L.; Goodwyn, L. W.; Weiss, B. "Equivalence of Topological Markov Shifts." Israel J. Math. 27, 49-63, 1977.Adler, R. L. and Weiss, B. Similarity of Automorphisms of the Torus. Providence, RI: Amer. Math. Soc., 1970.Trahtman, A. N. "道路着色问题。" 2007 年 12 月 21 日。 http://arxiv.org/abs/0709.0099.在 中被引用
道路着色问题请引用为
Weisstein, Eric W. "道路着色问题。" 来自 --一个 Wolfram 网络资源。 https://mathworld.net.cn/RoadColoringProblem.html