ライツアウトパズルを使って単純無向グラフにおけるマッチングの総数の偶奇を求める方法

グラフ理論,ライツアウト,マッチング

160

はじめに

ある単純無向グラフ $G$ が与えられたとき， $G$ のマッチングの総数の偶奇を求める方法を見つけたので紹介します．

本文

定義

本記事で用いる定義です．

単純無向グラフ

頂点集合 $V_{G}$ , 辺集合 $E_{G} \subseteq {{a, b} ∣ a, b \in V_{G}, a \neq b}$ の組を単純無向グラフとし， $G = (V_{G}, E_{G})$ で表す．

グラフ理論におけるマッチングの定義は以下の通りです．

マッチング

グラフ $G$ におけるマッチングとは，集合 $M_{G} \subseteq E_{G}$ であって， $M_{G}$ のどの $2$ つの元も，互いに頂点を共有していないものである．

グラフ $G$ におけるマッチングの総数は，トポロジカル・インデックス(細矢インデックス)という名前がついています．

トポロジカル・インデックス

$G$ におけるトポロジカル・インデックス $Z_{G}$ を以下で定義する．
$Z_{G} = \sum_{k = 0}^{n} # M_{G, k}$
ここで， $n$ は $G$ の頂点数であり，
$M_{G, k}$ は $G$ におけるマッチング $M_{G}$ であって $# M_{G} = k$ であるもの全ての集合である．

主張

先に結論から述べてしまいます．

単純無向グラフ $G$ の隣接行列を $A$ とする．このとき，以下が成立する．
$Z_{G} \equiv \det (A + I) (mod 2)$

基本的に， $Z_{G}$ そのものを求めるためには膨大な計算量を必要とするため，多項式時間では求めることができません(おそらく...というかそうじゃないとこの記事の意味がなくなるので困る)
しかし，この主張を用いることで $Z_{G}$ の偶奇であれば $O (n^{3})$ で求めることができます．

ライツアウト

ライツアウトとは

いきなり何？となるかもしれないですが，ここで，ライツアウトパズルについて説明します．
見たことある人も多いと思います．正方形の盤面があり，各マスが白黒で着色されています．マスを $1$ つ選んで操作を行うと，そのマスと，隣接しているマスの色が反転します，マスを上手く選び操作を施して，全てのマスの色を白色にするとクリアとなります．
ライツアウトの操作の例
このライツアウトですが，常に解くことができるわけではありません．
たとえば， $3 \times 3, 7 \times 7$ の盤面ではどの盤面からでもすべてのマスを白色にすることができるのですが， $4 \times 4, 5 \times 5$ の盤面では解けない配置が存在します．

ライツアウトの盤面を一般化する

単純無向グラフに色の情報を足したライツアウトグラフ(本記事独自の呼び方です)を以下のように定義します．

ライツアウトグラフ

頂点集合を $V_{G_{L}}$ , 辺集合を $E_{G_{L}} \subseteq {{a, b} ∣ a, b \in V_{G_{L}}, a \neq b}$ とする．
また，関数 ${Col}_{G_{L}} : V_{G_{L}} \to {0, 1}$ によって $V_{G_{L}}$ の各元が値を持っている．
このとき，ライツアウトグラフ $G_{L}$ を $G_{L} = (V_{G_{L}}, E_{G_{L}}, {Col}_{G_{L}})$ で表す．
ライツアウトグラフ全体の集合を $G$ とする．

ライツアウトグラフの各頂点に対する操作を次で定義します．

ライツアウトグラフの頂点に対する操作

また， $v \in V_{G_{L}}$ について定まる関数 ${Swap}_{v} : G \to G$ を以下で定義する．

${Swap}_{v} (G_{L}) = {Swap}_{v} ((V_{G_{L}}, E_{G_{L}}, {Col}_{G_{L}})) = (V_{G_{L}}, E_{G_{L}}, {Col}_{G_{L}}^{*})$
${Col}_{G_{L}}^{*} (v) = {\begin{cases} 0 if {Col}_{G_{L}} (v) = 1 \\ 1 otherwise \end{cases}$
$\begin{aligned} for each u \in V_{G_{L}} & s.t. u \neq v, {u, v} \in E_{G_{L}} : \\ {Col}_{G_{L}}^{*} (u) = {\begin{cases} 0 if {Col}_{G_{L}} (u) = 1 \\ 1 otherwise \end{cases} \end{aligned}$
$for each u \in V_{G_{L}} s.t. u \neq v, {u, v} \notin E_{G_{L}} : {Col}_{G_{L}}^{*} (u) = {Col}_{G_{L}} (u)$

長ったらしく書いていますが，要は $1$ つ頂点を選んだら，その頂点自身と，頂点と隣接している頂点の $0, 1$ を入れ替えると言っているだけです．
この操作は適用させる順番は関係なく，同じ頂点へ $2$ 回操作することは操作していないことと同じです．まぁ当たり前ですね．
もう一つ，ライツアウトグラフの解も定義しておきます．

ライツアウトグラフの解

$G^{*} = {(V, E, Col) \in G ∣ \forall v \in V, Col (v) = 0}$ とする．このとき，
$X_{G_{L}} = {v_{i} ∣ 0 \leq i \leq m \leq # V_{G_{L}}, {Swap}_{v_{1}} \circ {Swap}_{v_{2}} \circ \dots {Swap}_{v_{m}} (G_{L}) \in G^{*}}$ を $G_{L}$ における解とする．
ただし，条件を満たすような $v_{1}, v_{2}, \dots v_{m}$ が存在しないときは， $X_{G_{L}} = \emptyset$ とし， $G_{L}$ は解を持たないものとする.

すべての頂点の持つ値を $0$ にできたら勝ちってことです．
ようやくライツアウトグラフについての定義がおわりました．
ライツアウトグラフの例を $1$ つ載せます．
$\begin{aligned} G_{L} = (V_{G_{L}}, E_{G_{L}}, {Col}_{G_{L}}) \\ V_{G_{L}} = {1, 2, 3, 4}, E_{G_{L}} = {{1, 2}, {2, 3}, {3, 4}, {3, 1}}, \\ {Col}_{G_{L}} (1) = 0, {Col}_{G_{L}} (2) = 0, \\ {Col}_{G_{L}} (3) = 1, {Col}_{G_{L}} (4) = 0 \end{aligned}$
としてみます．
各頂点が持っている ${Col}_{G_{L}}$ の値について $0$ を白， $1$ を黒にして描画します．
ライツアウトグラフの例
この場合の $G_{L}$ における解は存在して， $X_{G_{L}} = {1, 3, 4}$ です．
正方形の盤面におけるライツアウトの自然な拡張となっていると思います．
グラフ版のライツアウトパズルの簡易的なエディタを作成しましたので載せておきます．興味のある人は触ってみるとちょっと楽しいかもしれないです．
グラフ版ライツアウト

ライツアウトグラフが常に解を持つかの判定

$G_{L} \in G$ について， $G_{L} = (V_{G_{L}}, E_{G_{L}}, {Col}_{G_{L}})$ とします．このとき， ${Col}_{G_{L}}$ の値の組み合わせの違いとして考えられる $2^{# V_{G_{L}}}$ 個のライツアウトグラフの集合を $G_{L}^{*}$ とします．
$G_{L}^{*}$ の要素の中には，少なくとも $1$ つは解をもつようなものが存在することは自明でしょうが， $V_{G_{L}}, E_{G_{L}}$ によっては， $G_{L}^{*}$ の要素すべてが解を持っているような場合もあります．
与えられたライツアウトグラフが，頂点の持っている値にかかわらず常に解を持っているための条件を求めてみましょう．
ここからの演算は特に断りのない限り， $F_{2}$ 上で行います．
また，簡単のため， $G_{L}$ の頂点数を $n := # V_{G_{L}}$ とします．
$G_{L}$ の各頂点について， ${Col}_{G_{L}} (v_{i})$ の値を並べた $n$ 次ベクトルを考え，このベクトルを $\vec{G_{L}}$ とします．
また， ${Swap}_{v_{i}}$ も同じように，色を変える頂点に対応する成分を $1$ ，それ以外を $0$ とすれば， $n$ 次ベクトルが作れます．このベクトルを $\vec{S_{v_{i}}}$ とします．
すると， $\vec{G_{L}} + \vec{S_{v_{i}}}$ によって得られるベクトルも， ${Swap}_{v_{i}} (G_{L})$ の各頂点における ${Col}_{{Swap}_{v_{i}} (G_{L})}$ の値を並べた $n$ 次ベクトルとなっています．
このことから，連立方程式
$\vec{G_{L}} + \sum_{i = 1}^{n} x_{i} \vec{S_{v_{i}}} = \vec{0}$
を，未知数 $x_{1}, x_{2}, \dots, x_{n}$ について解くことで，ライツアウトグラフの解を求めることができます．
また，この連立方程式が解を持たなければ，ライツアウトグラフの解は常に存在するとは言えないため，与えられたライツアウトグラフが，頂点の持っている値にかかわらず常に解を持っているための条件は，
$\det (S) = 1$
となります．ただし， $S$ は $\vec{S_{v_{1}}}, \vec{S_{v_{2}}}, \dots, \vec{S_{v_{n}}}$ を並べた $n$ 次正方行列です．
隣り合う頂点に対応する成分を $1$ にしていたため， $S$ は対称行列となります．
先ほど例に挙げたグラフで考えてみます．
$\vec{G_{L}} = (\begin{matrix} 0 \\ 0 \\ 1 \\ 0 \end{matrix}), \vec{S_{1}} = (\begin{matrix} 1 \\ 1 \\ 1 \\ 0 \end{matrix}), \vec{S_{2}} = (\begin{matrix} 1 \\ 1 \\ 1 \\ 0 \end{matrix}), \vec{S_{3}} = (\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \end{matrix}), \vec{S_{4}} = (\begin{matrix} 0 \\ 0 \\ 1 \\ 1 \end{matrix})$
であるため，
$S = (\begin{matrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{matrix})$
です．この行列は $G_{L}$ の隣接行列に単位行列を足したものです．
また， $G_{L}$ のすべての頂点に $1$ つずつループを付加したグラフの隣接行列としてみることもできます．
ここで， $\det (S)$ の定義を思い出します． $F_{2}$ で考えていたので，置換の符号は無視してよく，
$\det (S) = perm (S) = \sum_{σ \in S} \prod_{i = 1}^{n} S (i, σ (i))$
です．ただし， $S$ を $n$ 次対称群， $S$ の $(i, j)$ 成分を $S (i, j)$ としました．
行列式は， $S$ の成分から $1$ を選んでかけるような置換の選び方の個数として解釈できます．
さらに， $S$ は対称行列であり，対角成分について非対称な成分の選び方は偶数個存在します．
したがって，対角成分について対称な成分の選び方のみをカウントすればよいです．

マッチングとライツアウト

マッチングの話に戻ります．先ほど例に挙げたライツアウトグラフと同じ頂点と辺の組を持つ単純無向グラフ $G$ を例として話します．
$\begin{aligned} G = (V_{G}, E_{G}) \\ V_{G} = {1, 2, 3, 4}, E_{G} = {{1, 2}, {2, 3}, {3, 4}, {3, 1}} \end{aligned}$
ここで， $G$ のマッチング $M_{G}$ を
$M_{G} = {{1, 2}, {3, 4}}$
とします．この辺を赤く着色して次に示します．
マッチングの一例
$M_{G}$ の各要素について，辺で結ばれている頂点の組を入れ替えるように置換 $σ$ を定めます．
この例だと
$σ = (\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{matrix})$
です．この置換によってえらばれる $S$ の要素は
$S = (\begin{matrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{matrix})$
であり，対角成分について対称な選び方となっています．
一般に，各 $M_{G}$ に対して，異なる $σ$ が定まり，それらは全て対角成分について対称な選び方を与える置換となります．
逆に，対角成分について対称な選び方を与える $σ$ それぞれに対して，異なる $M_{G}$ が定まります．
したがって，
$\det (S) = # ⋃ M_{G} = Z_{G}$
です．
$G$ の隣接行列を $A$ とすると， $S = A + I$ であったため，冒頭の主張である
$Z_{G} \equiv \det (A + I) (mod 2)$
が示せました．