文献あり

PILAME杯本選Day1 P2の線形代数による解法＆一般化

226

まえがき

この記事では，グラフ理論における線形代数の応用例を紹介します.
閉路空間を用いてPILAME杯第１部問2の構成を自然に見つける方法の紹介と一般のグラフへの一般化を行います.
前提知識としてグラフ理論と線形代数の基本的な知識を要求しています.
また，この記事を書くに当たって[1]を参考にしました．

問題

今回議論するのは，以下の問題です.

PILAME杯第１部問2

N を 3 以上の整数とする．N 人の人がおり，最初はどの 2 人も互いに友人ではないとする．以下のようなイベントを何回か起こすことで，どの 2 人も互いに友人であるようにできるような N をすべて求めよ．

N 人のうちの 3 人を選び，A, B, C とする．2 人組 (A, B), (B, C), (C, A) それぞれについて，互いに友人である場合は互いに友人でなくなり，互いに友人でない場合は互いに友人になる．

これを言い換えると，次のようになります.

グラフで言い換え

頂点集合を $V = \{1,2, \cdots , N\}$，辺集合を $E = \emptyset$ とするグラフ $G$ がある．以下の操作を何回か起こすことで，$G = K_N$(完全グラフ)とできるような $N$ を全て求めよ.

相異なる $a,b,c \in V$ を選び，$E$ を $E \bigtriangleup \{\{a,b\},\{b,c\},\{c,a\}\}$ にする($\bigtriangleup$ は集合の対称差(xor)を表す).

さらに言い換えると，次のようになります.

グラフで言い換え2

頂点集合を $V = \{1,2, \cdots , N\}$，辺集合を $E = \{\{a,b\} \mid a,b \in V,a \neq b\}$ とする完全グラフ $K_N$ について, $K_N$ の部分閉路で長さが $3$ であるようなもの(の辺集合)全体の集合を $cyc_3$ とする.$cyc_3$ のいくつかの元の対称差で表すことのできる $E$ の部分集合全体の集合を $C_3$ とする(ただし$\emptyset \in C_3$とする).$E \in C_3$(グラフと辺集合を同一視すれば$K_N \in C_3$とも書ける) であるような $N$ を求めよ.

PILAME杯第１部問2の答え

<行間>
自分で考えたい人は今のうちに

</行間>

各頂点の次数の偶奇を考えることで$N$が偶数の時は不適であることがわかる.
$N$が奇数のときは，頂点に$1$から$N$までの数を割り振っておいて「$(A,B,C) = (1,a,b)$として操作を行う」を全ての$1< a< b$について行えばよい.
よって$N = (奇数)$

線形代数による自然な別解

上記の構成は少々天下り的で応用も効きづらそうです.以下では線形代数による構成をしない解答とそこから構成を見つける方法を紹介します(本番もこれで解きました).
以降グラフは単純かつ無向であるとします.

辺空間

ある集合$S$の部分集合全体の集合$2^S$は，対称差(排他的論理和)を和，$0,1 \in \mathbb{F}_2,x \in 2^S$について積を$1 \cdot x = x, 0 \cdot x = \emptyset$と定義することによって$\mathbb{F}_2$上のベクトル空間となります.

辺空間

グラフ$G$の辺集合$E = E(G)$の部分集合全体のなすベクトル空間を辺空間という.

以降，$G$の部分グラフをその辺集合と同一視します.
$G$の2つの偶部分グラフの対称差もまた$G$の偶部分グラフで，偶グラフはいくつかの閉路の非交和で表すことができるので，次のようなものを考えられます.

閉路空間

無向グラフ$G$の偶部分グラフ全体のなすベクトル空間を閉路空間という.閉路空間は$G$の部分閉路によって生成される辺空間の部分空間である.

少し前の「グラフで言い換え2」で出てきた$C_3$は長さ3の閉路で生成される閉路空間の部分空間となります.
今から任意の$N$で$C_3$と$K_N$の閉路空間が一致することを示し，そこから$K_N$は$N$が奇数のとき自分自身の偶部分グラフなので$K_N \in C_3$であるということを導きます.
そのために，閉路空間の次元を調べます.

閉路空間の次元

閉路空間とボンド空間は直交する

閉路空間を辺空間の部分空間とみなしたとき，閉路空間はボンド空間の直交補空間である.

少々長くなるのでボンド空間についての解説は省略します(この定理の詳細はいつかは書くと思います，私がグラフ理論にハマったきっかけです).
連結グラフのボンド空間の次元は$n - 1$です($n$は$G$の頂点数).今回欲しいのはここから得られる次の系です.

連結グラフ$G$の閉路空間の次元は$|E| - n + 1$である.

lockerさんが定理1を使わず系1を示しています ,ぜひ読んでみてください！.

閉路空間の基底

グラフ$G$の全域木$T$について基本閉路というものが定義でき，これが基底となります.

基本閉路

グラフ$G$の全域木$T$と$e \in E \setminus T$について，$T\cup \{e\}$はただ一つの閉路を持つ.これを$T$(あるいは$e$について)の基本閉路と呼ぶ.

定理名（任意）

グラフ$G$の任意の全域木$T$について，$T$についての基本閉路全体の集合は$G$の閉路空間の基底である.

$T$の$e$についての基本閉路$c$は他のどの$T$の基本閉路も持たない辺$e$を持っているので線形独立である.
$T$の基本閉路は$|E| - n + 1$個あり，これは閉路空間の次元に等しい.
よって示された.

$K_N$の全域木として，頂点1と他の全ての頂点を結ぶものを考えます.このとき基本閉路はすべて長さが3になります.よって$C_3$は閉路空間となります.
完全グラフにおいて$C_3$は閉路空間と一致することがわかりました.$K_N$は$N$が奇数のとき自分自身の偶部分グラフなので$K_N \in C_3$，そうでないとき$K_N \not\in C_3$です.よって示されました.
またここから$N$が奇数のとき基本閉路全ての対称差が$K_N$となることがわかるので，構成が得られます.