Road Coloring Problem
昨日の記事ですが，Road Coloring Problem (Road Coloring 予想) と呼ばれるグラフ理論の定理が証明された事の紹介があったようです．グラフ理論については不勉強なもので今までこの問題を知らなかったのですが，主張しているのは以下のようなことです．
Road Coloring 予想：各頂点が一定の出次数を持つ強連結非周期的*1有限有向グラフには必ず同期的彩色*2（synchronizing coloring）が存在する．
同期的彩色とは枝の彩色で，グラフの各頂点 v に対して色の系列 c(v) が存在して，どの頂点からスタートしても c(v) に従って進む枝を選んでいくと最終的に v に到達するというものです．例えばある頂点 w に「青赤青赤青赤」という色の系列が対応しているとすると，どの頂点からも「青赤青赤青赤」の順で枝を辿ると w に到達するということです．より具体な例は英語版wikipediaのRoad coloring problemの項目を参照して下さい．論文もチラリと眺めてみたのですが，そこまで高度な数学を要求していないようで，割と簡潔にまとめられていました．確かに結果を聞くと「へ〜」という感じなのですが，こういう結構マニアックな内容がスラッシュドットに取り上げられたのも驚きです．
