1998年東京大学後期第3問を一般化した

グラフ理論,1998年東京大学後期第3問

この記事は1998年東京大学後期第3問(例のグラフ理論のやつ)を発展させたものなので、先に元の問題と解説を読んでおくことを推奨します。

主定理

この記事では以下の定理を証明します。

「 $N$ 個の $\circ$ と $∙$ が $1$ 行に並んだグラフに対し、それが可能グラフかどうか判定し、可能グラフであるときは操作の順を出力せよ。」という問題は $O (N)$ の時間計算量で解ける。

証明

定義

頂点の最大次数が $2$ である木のことを $1$ 行グラフと呼ぶ。

グラフ $G = (V, E)$ に対しグラフ $G^{'} = (V^{'}, E^{'})$ を作る操作 $2^{'}$ を以下で定義する:

この操作は $G$ の頂点 $P_{i_{0}}$ であって、以下の条件を満たすものを $1$ つ選ぶと定まる。
- $P_{i_{0}}$ の色は白である。
- $P_{i_{0}}$ を頂点に持つ辺は丁度 $2$ 個存在する。
  - これらの辺の頂点のうち $P_{i_{0}}$ ではない方をそれぞれ $P_{i_{1}}, P_{i_{2}}$ とする。
$V^{'}$ は $V$ から $P_{i_{0}}$ を取り除いたものである。
$W^{'}$ は $W$ から $P_{i_{0}}$ を頂点に持つ辺を取り除き、新しい辺 $E_{m + 1}$ を加えたものとする。
- $E_{m + 1}$ の頂点は、 $P_{i_{1}}$ と $P_{i_{2}}$ である。
$G^{'}$ のそれ以外での辺の頂点は $G$ での対応する辺の頂点と同じにする。
$G$ において頂点 $P_{i_{1}}$ の色が白又は黒ならば、 $G^{'}$ における色はそれぞれ黒又は白に変化させる。 $P_{i_{2}}$ についても同様に変化させる。それ以外の頂点の色は変化させない。

グラフによっては操作 $2^{'}$ を行うための頂点 $P_{i_{0}}$ を選べないことがあるが、その場合は操作 $2^{'}$ は行えないものとする。

$\circ - \circ - ∙ \Rightarrow ∙ - \circ$
$\circ - \circ - \circ \Rightarrow ∙ - ∙$
$\circ - \circ - \circ - \circ \Rightarrow \circ - ∙ - ∙$
$\circ - \circ - \circ - \circ \Rightarrow ∙ - ∙ - \circ$

操作 $2^{'}$ は操作 $2$ の逆操作である。すなわち、グラフ $G$ に操作 $2^{'}$ を行ってグラフ $G^{'}$ を得たとき、グラフ $G^{'}$ に操作 $2$ を行ってグラフ $G$ を得ることができる。

以下では、便宜上 $1$ 行グラフの片方を左側、もう片方を右側とし、各操作でこの左右は固定されるものとする。

長さ $4$ 以上の $1$ 行グラフ $G$ に対し、 $1$ 行グラフ $G^{'}$ を作る操作 $R$ を次で定義する:

右端以外で $∙ - \circ$ という箇所があれば、そのうち最も右にあるものの $\circ$ に対する操作 $2^{'}$
そうでなくて、左端以外で $\circ - ∙$ という箇所があれば、そのうち最も右にあるものの $\circ$ に対する操作 $2^{'}$
そうでないとき、両端以外は全て $\circ$ である。
- 両端以外の $\circ$ が $3$ 個以上あれば、右から $4$ 番目の頂点となる $\circ$ に対する操作 $2^{'}$
- このグラフに対して操作 $R$ は行えないとする。

この操作 $R$ には、次の性質がある:

操作後に両端以外の $\circ$ がなくなることはない。
操作が行えないグラフは、以下の場合に限られる( $⋆$ は $\circ$ または $∙$ ):
- $⋆ - ∙ - ∙ - \dots - ∙ - ⋆$ 、ただし $⋆$ は $\circ$ または $∙$
- $⋆ - \circ - \circ - ⋆$
- $⋆ - \circ - ⋆$

これを上から順に $(G 1), (G 2), (G 3)$ とする。

グラフ $G$ に対し、操作 $R$ を適用できなくなるまで繰り返し適用することで得られるグラフを $G$ の種グラフと呼ぶ。

種グラフは必ず $(G 1), (G 2), (G 3)$ のどれかになる。

分類

不変量を使って任意の可能グラフに対する種グラフが $(G 3)$ であることを示す。そのために、元の問題で使われた不変量を拡張する。

$1$ 行グラフ $G$ に対する拡張不変量を、 $G$ の $4$ 通りの追加グラフに対する
$(交代和を 3 で割った余り, ∙ の個数を 2 で割った余り)$
からなる多重集合とする。

$\circ$ に対する拡張不変量は、 ${| (0, 0), (2, 1), (1, 1), (2, 0) |}$ である。
$\circ - ∙$ に対する拡張不変量は、 ${| (1, 1), (2, 0), (0, 0), (2, 1) |}$ である。
$\circ - \circ$ に対する拡張不変量は、 ${| (1, 0), (0, 1), (0, 1), (1, 0) |}$ である。

$1$ 行グラフに操作 $2$ を行っても、拡張不変量は変わらない。

証明は元の問題と同じようにできるので読者への演習問題とします。

全ての可能グラフの追加グラフの種グラフは $(G 3)$ である。

明らかに全ての可能グラフには少なくとも $1$ 個の $\circ$ があるので、追加グラフには両端以外に $\circ$ が存在する。よってその種グラフは $(G 1)$ ではない。

可能グラフに対する拡張不変量は ${| (0, 0), (2, 1), (1, 1), (2, 0) |} (:= A)$ である。しかし、 $\circ - \circ$ に対する拡張不変量は、 ${| (1, 0), (0, 1), (0, 1), (1, 0) |} (:= B)$ である。

仮に追加グラフの種グラフ $G^{'}$ が $(G 2)$ であるような可能グラフ $G$ が存在するとすると、 $\circ - \circ$ の両端に $1$ 個ずつ頂点を追加して $G^{'}$ を作れ、そこから操作 $2$ を繰り返すことで $G$ の追加グラフが得られるため、 $G$ の拡張不変量は $B$ となる。しかし $A \neq B$ であるからこれは矛盾である。

可能グラフでない $1$ 行グラフの追加グラフの種グラフが $(G 3)$ となることはない。

背理法で証明する。仮にそのようなグラフ $G$ が存在したとすれば、 $(G 3)$ から操作 $R$ を逆順にたどることで操作 $2$ の繰り返しとして $G$ の追加グラフが作れる。すなわち $G$ は可能グラフであるが、これは矛盾である。

定理4,定理5

与えられたグラフ $G$ が可能グラフかどうかを判定するためには、種グラフが $(G 3)$ であるかを判定すればよい。また、可能グラフである場合は、各回の操作 $R$ を逆順にたどることで、具体的な構成法が得られる。 $G$ の頂点数を $N$ とすると、その時間計算量は $O (N)$ である。