nkhrlab~

280字超の記事

勝敗グラフと有向閉路の存在性

勝敗グラフ

本記事における勝敗グラフを次のように定義する.勝敗グラフは有向グラフの一種である.

頂点集合 V,辺集合 Aを持つ有向グラフ G = (V, A)を考える.
 i, j \in Vに対し a_{i, j}を次のように定義する.
 a_{i, j} = \begin{cases} 1 & \left((i, j) \in A\right) \\ 0 & \left((i, j) \notin A\right)  \end{cases}.

 Gが次に示す条件を満たすとき,かつその場合に限り, G勝敗グラフである.
 \forall i, j \in V, a_{i, j} + a_{j, i} =  \begin{cases} 0 & \left(i = j\right) \\ 1 & \left(i \neq j\right)  \end{cases}.

本記事の主張

次の命題は勝敗グラフGが有向閉路を持つことの必要十分条件である.
 \exists i, j, k \in V, a_{i, j} + a_{j, k} + a_{k, i} = 3.

証明

Gが有向閉路を持つことを, \mathrm{Cycle}(G)と表すことにする.

十分性の証明

 a_{x, y} + a_{y, z} + a_{z, x} = 3を仮定する.
このとき,a_{i, j}の定義から,Gには辺(x, y), (y, z), (z, x)が存在する.この 3辺が長さ 3の有向閉路をなすので,
 \exists i, j, k \in V, a_{i, j} + a_{j, k} + a_{k, i} = 3 \Rightarrow \mathrm{Cycle}(G).

必要性の証明

 \mathrm{Cycle}(G)が真であると仮定する.
勝敗グラフの定義から, Gは長さ 1および長さ 2の有向閉路をもたない.よって, Gは長さ 3以上の有向閉路をもつ.

 Gが長さ 3の有向閉路をもつと仮定し,そのひとつをなす 3頂点を順に x, y, zとおくと,Gには辺(x, y), (y, z), (z, x)が存在するので,
 a_{x, y} = a_{y, z} = a_{z, x} = 1.
よって,
 a_{x, y} + a_{y, z} + a_{z, x} = 3.
したがって, Gが長さ 3の有向閉路をもつとき, \exists i, j, k \in V, a_{i, j} + a_{j, k} + a_{k, i} = 3.

 n \geq 4について, Gが長さ nの有向閉路をもつと仮定し,そのひとつをなす n頂点を順に x_1, x_2, \dots, x_nとおく.このとき,Gには辺(x_1, x_2), (x_2, x_3), (x_3, x_4), \dots, (x_{n-1}, x_n), (x_n, x_1)が存在する.
ここで, x_1 x_3に着目する.勝敗グラフとa_{i, j}の定義から, (a_{x_1, x_3}, a_{x_3, x_1}) = (1, 0)または (a_{x_1, x_3}, a_{x_3, x_1}) = (0, 1)のいずれかが成り立つ.
 (a_{x_1, x_3}, a_{x_3, x_1}) = (1, 0)と仮定すると,Gには辺(x_1, x_3)が存在する.よって,Gには辺(x_1, x_3), (x_3, x_4), \dots, (x_{n-1}, x_n), (x_n, x_1)が存在するので,Gには頂点 x_1, x_3, x_4, \dots, x_nからなる長さ n - 1の閉路が存在する.
 (a_{x_1, x_3}, a_{x_3, x_1}) = (0, 1)と仮定すると,Gには辺(x_3, x_1)が存在する.よって,Gには辺(x_1, x_2), (x_2, x_3), (x_3, x_1)が存在するので,Gには頂点 x_1, x_2, x_3からなる長さ 3の閉路が存在する.

帰納的に, \mathrm{Cycle}(G) \Rightarrow \exists i, j, k \in V, a_{i, j} + a_{j, k} + a_{k, i} = 3.

必要性と十分性が示されたので, \mathrm{Cycle}(G) \Leftrightarrow \exists i, j, k \in V, a_{i, j} + a_{j, k} + a_{k, i} = 3.

以上のことから,次の命題は勝敗グラフGが有向閉路を持つことの必要十分条件である.
 \exists i, j, k \in V, a_{i, j} + a_{j, k} + a_{k, i} = 3.
逆に,次の命題は勝敗グラフGが有向閉路を持たないことの必要十分条件である.
 \forall i, j, k \in V, a_{i, j} + a_{j, k} + a_{k, i} \leq 2.