道路彩色定理

グラフ理論において、道路彩色定理（以前は道路彩色予想と呼ばれていた）は、同期された指示を扱う。問題は、そのような指示を使用することで、ネットワーク（市街地の道路や迷路の表現かもしれない）内の任意の地点からオブジェクトまたは目的地に到達したり、その場所を特定したりできるかどうかである。 ^[1]現実世界では、この現象は、友人に電話して家までの道順を尋ねたところ、どこから出発しても同じ道順を教えてくれたようなものである。この定理は、記号力学にも影響を与えている。

この定理はロイ・アドラーとベンジャミン・ワイスによって最初に推測された。^[2]アブラハム・トラハトマンによって証明された。^[3]

右の画像は、各頂点の出力次数が 2 である8 つの頂点を持つ有向グラフを示しています 。(この場合、各頂点の入次数も 2 ですが、同期カラーリングが存在するためには、これは必須ではありません。) このグラフのエッジは、同期カラーリングを作成するために赤と青で色付けされています。

たとえば、黄色でマークされた頂点を考えてみましょう。グラフのどこから始めても、「青-赤-赤—青-赤-赤—青-赤-赤」の経路で 9 つの辺すべてをたどると、黄色の頂点に到達します。同様に、「青-青-赤—青-青-赤—青-青-赤」の経路で 9 つの辺すべてをたどると、どこから始めても、常に緑色でマークされた頂点に到達します。

道路着色定理は、特定のカテゴリの有向グラフに対して、常にそのような着色を作成できることを示しています。

G を有限で強く連結された有向グラフとし、すべての頂点の出力次数 k が同じであるとします。Aを文字 1、...、k を含むアルファベットとします。Gの同期彩色(折りたたみ可能彩色とも呼ばれる) は、 (1) 各頂点には、特定のラベルが付いた出力エッジが1 つだけあり、(2)グラフ内のすべての頂点vに対して、 A上の単語wが存在し、 wに対応するG内のすべてのパスがvで終了するように、 A の文字で Gの辺にラベルを付けることです。

同期着色という用語は、この概念と有限オートマトン理論 における同期語の概念との関係によるものです。

このような色付けが存在するためには、Gが非周期的であることが必要である。^[4]道路色付け定理によれば、このような色付けが存在するためには非周期性も必要である。したがって、道路色付け問題は次のように簡単に述べることができる。

均一な出次数の有限の強連結非周期グラフはすべて同期着色を持ちます。

これまでの部分的または特殊なケースの結果には、次のようなものがあります。

• Gが多重辺を持たない有限の強連結非周期有向グラフであり、GがGの真部分集合である素数長さの単純サイクルを含む場合、Gは同期着色を持つ。^[5]
• Gが有限の強連結非周期有向グラフ（複数の辺が許される）であり、すべての頂点が同じ入次数と出次数kを持つ場合、Gは同期着色を持つ。^[6]

• 四色定理
• グラフの色付け

• アドラー、ロイ L. ;ワイス、ベンジャミン(1970)、「トーラスの自己同型の類似性」、アメリカ数学会誌、第 98 巻、doi :10.1090/memo/0098。
• Hegde, Rajneesh; Jain, Kamal (2005)、「道路着色予想に関する最小最大定理」、Proc. EuroComb 2005 (PDF)、離散数学と理論計算機科学、pp. 279–284。
• カリ、ヤルッコ(2003)、「オイラー有向グラフ上の有限オートマトン同期」、理論計算機科学、295 (1–3): 223–232、doi : 10.1016/S0304-3975(02)00405-X。
• オブライエン、GL（1981）、「道路着色問題」、イスラエル数学ジャーナル、39（1–2）：145–154、doi：10.1007 / BF02762860。
• トラハトマン、アブラハム N. (2009)、「道路の色分け問題」、イスラエル数学ジャーナル、172 (1): 51–60、arXiv : 0709.0099、doi : 10.1007/s11856-009-0062-5。