在上面的有向圖中，選擇任意頂點並按藍-紅-紅的順序沿著箭頭走三次。您將始終到達綠色頂點。 類似地，按藍-藍-紅的順序走三次，無論您從哪裡開始，都將始終到達黃色頂點。 這被稱為同步著色。
道路著色問題是同步著色一個有向有限強連通圖的問題，該圖具有相同的出度，並且所有環長度的最大公約數為 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.tw/RoadColoringProblem.html