この記事は1998年東京大学後期第3問(例のグラフ理論のやつ)を発展させたものなので、先に 元の問題と解説 を読んでおくことを推奨します。
この記事では以下の定理を証明します。
「$ N $個の$ \circ $と$ \bullet $が$ 1 $行に並んだグラフに対し、それが可能グラフかどうか判定し、可能グラフであるときは操作の順を出力せよ。」という問題は$ O(N) $の時間計算量で解ける。
頂点の最大次数が$ 2 $である木のことを$ 1 $行グラフと呼ぶ。
グラフ$ G = (V, E) $に対しグラフ$ G' = (V', E') $を作る操作$ 2' $を以下で定義する:
グラフによっては操作$ 2' $を行うための頂点$ P_{i_0} $を選べないことがあるが、その場合は操作$ 2' $は行えないものとする。
$ \circ - \circ - \bullet \Rightarrow \bullet - \circ $
$ \circ - \circ - \circ \Rightarrow \bullet - \bullet $
$ \circ - \circ - \circ - \circ \Rightarrow \circ - \bullet - \bullet $
$ \circ - \circ - \circ - \circ \Rightarrow \bullet - \bullet - \circ $
操作$ 2' $は操作$ 2 $の逆操作である。すなわち、グラフ$ G $に操作$ 2' $を行ってグラフ$ G' $を得たとき、グラフ$ G' $に操作$ 2 $を行ってグラフ$ G $を得ることができる。
以下では、便宜上$ 1 $行グラフの片方を左側、もう片方を右側とし、各操作でこの左右は固定されるものとする。
長さ$ 4 $以上の$ 1 $行グラフ$ G $に対し、$ 1 $行グラフ$ G' $を作る操作$ R $を次で定義する:
この操作$ R $には、次の性質がある:
これを上から順に$ (G1), (G2), (G3) $とする。
グラフ$ G $に対し、操作$ R $を適用できなくなるまで繰り返し適用することで得られるグラフを$ G $の種グラフと呼ぶ。
種グラフは必ず$ (G1), (G2), (G3) $のどれかになる。
不変量を使って任意の可能グラフに対する種グラフが$ (G3) $であることを示す。そのために、元の問題で使われた不変量を拡張する。
$ 1 $行グラフ$ G $に対する拡張不変量を、$ G $の$ 4 $通りの追加グラフに対する
$ (\text{交代和を}3\text{で割った余り}, \bullet\text{の個数を}2\text{で割った余り}) $
からなる多重集合とする。
$ \circ $に対する拡張不変量は、$ \{\!| (0, 0), (2, 1), (1, 1), (2, 0) |\!\} $である。
$ \circ - \bullet $に対する拡張不変量は、$ \{\!| (1, 1), (2, 0), (0, 0), (2, 1) |\!\} $である。
$ \circ - \circ $に対する拡張不変量は、$ \{\!| (1, 0), (0, 1), (0, 1), (1, 0) |\!\} $である。
$ 1 $行グラフに操作$ 2 $を行っても、拡張不変量は変わらない。
証明は元の問題と同じようにできるので読者への演習問題とします。
全ての可能グラフの追加グラフの種グラフは$ (G3) $である。
明らかに全ての可能グラフには少なくとも$ 1 $個の$ \circ $があるので、追加グラフには両端以外に$ \circ $が存在する。よってその種グラフは$ (G1) $ではない。
可能グラフに対する拡張不変量は$ \{\!| (0, 0), (2, 1), (1, 1), (2, 0) |\!\} (:=A) $である。しかし、$ \circ - \circ $に対する拡張不変量は、$ \{\!| (1, 0), (0, 1), (0, 1), (1, 0) |\!\} (:=B) $である。
仮に追加グラフの種グラフ$ G' $が$ (G2) $であるような可能グラフ$ G $が存在するとすると、$ \circ - \circ $の両端に$ 1 $個ずつ頂点を追加して$ G' $を作れ、そこから操作$ 2 $を繰り返すことで$ G $の追加グラフが得られるため、$ G $の拡張不変量は$ B $となる。しかし$ A \neq B $であるからこれは矛盾である。
可能グラフでない$ 1 $行グラフの追加グラフの種グラフが$ (G3) $となることはない。
背理法で証明する。仮にそのようなグラフ$ G $が存在したとすれば、$ (G3) $から操作$ R $を逆順にたどることで操作$ 2 $の繰り返しとして$ G $の追加グラフが作れる。すなわち$ G $は可能グラフであるが、これは矛盾である。
与えられたグラフ$ G $が可能グラフかどうかを判定するためには、種グラフが$ (G3) $であるかを判定すればよい。また、可能グラフである場合は、各回の操作$ R $を逆順にたどることで、具体的な構成法が得られる。$ G $の頂点数を$ N $とすると、その時間計算量は$ O(N) $である。
もし次回があれば$ 1 $行ではないグラフについて書きます。