トーナメントグラフへの準同型：非巡回性

今度は，有向グラフ(各辺に向きが付いているグラフ)の準同型について考えてみよう． 有向グラフの場合の準同型は，辺を向きも込めて保存する写像である． つまり，f:G→Hが準同型とは，Gの頂点集合からHの頂点集合への写像で， Gにu→vいう有向辺があるときに，Hにf(u)→f(v)という有向辺が必ずあるようなもののことである．

2章では完全グラフK_nへの準同型が彩色と関連があることを見ているが， ここでは，完全グラフに向きをつけたグラフを考えてみよう． 向き付けとしては，まず頂点に1,2,...,nと番号を振り，小さい方から大きい方へ向き付ける．このようなグラフはトーナメントグラフ T_nと呼ばれている．

このトーナメントグラフには，向きの付け方から明らかなように，有向サイクル(辺の向きに沿って一周してくることができるサイクル)が存在しない．

グラフGから(あるサイズの)トーナメントグラフT_nへの準同型fがあったとする．
このとき，もしグラフGに有向サイクルu₁→u₂→u₃→…→u_t→u₁があったとすると， f(u₁)→f(u₂)→f(u₃)→…→f(u_t)→f(u₁)がT_n中の有向サイクルになってしまい，矛盾となる． したがって，グラフGには有向サイクルが存在しない，つまり，非巡回的(acyclic)であることが分かる．

逆に，グラフGが非巡回的であったとする．
このとき，グラフGの各頂点に次のような順番付けを与えることができる．

• 有向辺u→vが存在する2頂点に関して，必ずuの方がvより小さい番号になる．

つまり，次の性質が成り立つことが分かった．

性質： 有向グラフGから(あるサイズの)トーナメントグラフへの準同型が存在することと， Gが非巡回的であることは等価である．