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

勝敗グラフ

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

頂点集合 $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.$

nkhrlab~

140字超の記事

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