道路彩色定理
グラフ理論において、道路彩色定理（以前は道路彩色予想として知られていた）は、同期した指示を扱う。問題は、そのような指示を用いることで、ネットワーク（街路や迷路などの表現）内の任意の地点から、ある物体や目的地に到達したり、その場所を特定したりできるかどうかである。[ 1 ]現実世界では、この現象は、友人に電話して家への道を尋ねたところ、どこから出発しても通用する一連の道順を教えてくれるようなものである。この定理は、記号力学にも影響を与えている。
この定理はロイ・アドラーとベンジャミン・ワイスによって最初に予想された。[ 2 ]アブラハム・トラハトマンによって証明された。[ 3 ]
例と直感
右の画像は、各頂点の出力次数が 2 である8 つの頂点を持つ有向グラフを示しています 。(この場合、各頂点の入次数も 2 ですが、同期カラーリングが存在するためには、これは必須ではありません。) このグラフのエッジは、同期カラーリングを作成するために赤と青で色付けされています。
例えば、黄色でマークされた頂点を考えてみましょう。グラフのどこから始めても、「青-赤-赤-青-赤-青-赤-青-赤」という経路の9つの辺をすべて通れば、黄色の頂点に到達します。同様に、「青-青-赤-青-青-赤-青-青-赤」という経路の9つの辺をすべて通れば、どこから始めても、必ず緑色でマークされた頂点に到達します。
道路彩色定理は、有向グラフの特定のカテゴリでは、常にそのような彩色を作成できることを示しています。
数学的記述
G を有限で強く連結された有向グラフとし、すべての頂点の出力次数k が同じであるとする。Aを文字 1, ..., kを含むアルファベットとする。Gの同期彩色（折り畳み可能彩色とも呼ばれる）とは、 Gの辺を A の文字でラベル付けしたもので、( 1 ) 各頂点には、特定のラベルが付いた出力辺が 1 つだけあり、(2) グラフ内の頂点vごとに、 A上の単語wが存在し、 wに対応するGのすべてのパスがvで終了する。
同期カラーリングという用語は、この概念と有限オートマトン理論における同期語の概念との関係に起因します。
このような彩色が存在するためには、Gが非周期的であることが必要である。[ 4 ]道路彩色定理によれば、このような彩色が存在するためには非周期性も必要である。したがって、道路彩色問題は簡潔に次のように表現できる。
- 均一な出次数の有限の強連結非周期グラフはすべて同期カラーリングを持ちます。
前回の部分的な結果
これまでの部分的または特殊なケースの結果は次のとおりです。
- G が多重辺を持たない有限の強連結非周期有向グラフであり、G がGの真部分集合である素数長さの単純閉路を含む場合、G は同期着色を持つ。[ 5 ]
- Gが有限の強連結非周期有向グラフ（複数の辺が許される）であり、すべての頂点が同じ入次数と出次数kを持つ場合、Gは同期着色を持つ。[ 6 ]
参照
注記
- ^ Seigel-Itzkovich, Judy (2008年2月8日). 「ロシア移民が数学パズルを解く」 . The Jerusalem Post . 2024年11月1日閲覧。
- ^アドラー＆ワイス 1970 .
- ^トラハトマン 2009 .
- ^ヘグデ＆ジェイン 2005 .
- ^オブライエン1981年。
- ^カリ 2003 .
参考文献
- アドラー、ロイ L. ;ワイス、ベンジャミン(1970)、「トーラスの自己同型の類似性」、アメリカ数学会誌、第 98 巻、doi : 10.1090/memo/0098。
- ヘグデ、ラジニーシュ、ジェイン、カマル (2005)、「道路彩色予想に関する最小最大定理」、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。
