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

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

今回は白丸が長方形状に並ぶグラフについて考えます。

主定理

白丸が長方形状に並ぶグラフのうち、どのように線を配置しても可能グラフにできないものは次の$ 3 $種類に限られる:

$ 1 \times (3m + 2) $、ただし$ m $は非負整数
$ 2 \times 2 $

証明

長方形の大きさを$ n \times m $とします。

$ n = 1 $のときは元の問題ですでに示されているので、$ n \geq 2 $のときを示します。

補題

任意のグラフの頂点に対し、少なくとも$ 1 $方向が空いていれば、そこに$ \circ - \circ - \circ $を追加することができる(以下ではこの操作を操作$ T $と呼ぶ)。

\begin{align*} & ? - \star \\ \Rightarrow & ? - \bar{\star} - \circ \\ \Rightarrow & ? - \star - \circ - \bullet \\ \Rightarrow & ? - \star - \circ - \circ - \circ \\ \end{align*}

ただし$ ? $は残りの部分、$ \star $は$ \circ $または$ \bullet $、$ \bar{\star} $は$ \star $の色を反転したもの。

$ n \times m $の長方形が作れるならば、$ (n + 3) \times m $と$ n \times (m + 3) $の長方形も作れる(以下ではこの操作を操作$ T' $と呼ぶ)。

$ n \times m $の長方形の$ 1 $個の辺を構成する全ての頂点に操作$ T $を適用すればよい。

$ n = 2 $のとき

$ m = 2 $のとき

$ 2 \times 2 $の$ \circ $だけの長方形を作ることはできない。

操作$ 2 $を行うと$ 3 $個以上の頂点が一直線上に並ぶので$ 2 \times 2 $の長方形を作るためには操作$ 1 $のみで行う必要がある。操作$ 1 $は$ \bullet $の個数の偶奇を反転させるが、頂点が$ 4 $個あるグラフでは操作$ 1 $が$ 3 $回必要であり、したがって$ \bullet $の個数は奇数でなければならない。よって、$ 4 $個すべての頂点を$ \circ $にすることはできない。

$ 2 \times 3 $の$ \circ $だけの長方形は作ることができる。

以下の過程で作れる。

\begin{eqnarray*} & \begin{array}{c} \circ \\ \end{array} \\ \\ \Rightarrow\ & \begin{array}{c} \bullet & - & \circ\\ \end{array} \\ \\ \Rightarrow\ & \begin{array}{c} \circ & & \\ | & & \\ \circ & - & \circ \\ \end{array} \\ \\ \Rightarrow\ & \begin{array}{c} \bullet & - & \circ \\ | & & \\ \circ & - & \circ \\ \end{array} \\ \\ \Rightarrow\ & \begin{array}{c} \circ & - & \circ & - & \bullet \\ | & & & & \\ \circ & - & \circ & & \\ \end{array} \\ \\ \Rightarrow\ & \begin{array}{c} \circ & - & \circ & - & \circ \\ | & & & & | \\ \circ & - & \circ & & \circ \\ \end{array} \end{eqnarray*}

任意の$ 3 $以上の整数$ m $に対し、$ 2 \times m $の$ \circ $だけの長方形は作ることができる。

「最も右下にある$ \circ $の上と右に操作$ 1 $を適用する」という操作を繰り返すことで、以下のグラフが得られる:

\begin{array}{c} \circ & & \circ & & & & \circ & & \\ | & & | & & \cdots & & | & & \\ \circ & - & \circ & - & & - & \circ & - & \circ \end{array}

ただし、$\ \begin{array}{c} \circ \\ | \\ \circ \end{array}\ $は$ m - 3 $個存在する。

このグラフの最も右下の頂点に定理5の証明の構成法と同じものを適用すれば、$ 2 \times m $の長方形が得られる。

$ n = 3 $のとき

任意の正整数$ m $に対し、$ 3 \times m $の$ \circ $だけの長方形は作ることができる。

$ m \% 3 = 0, 1 $であれば、$ 1 \times m $のグラフの上下に$ \circ $を追加すればよい:

\begin{array}{c} \circ & & \circ & & \circ \\ | & & | & & | \\ \circ & - & \circ & \cdots & \circ \\ | & & | & & | \\ \circ & & \circ & & \circ \\ \end{array}

$ m \% 3 = 2 $であれば、まず$ 2 \times 3 $の操作を転置して$ 3 \times 2 $を作り、そこから操作$ T' $を繰り返せばよい。

もちろん別解も存在し、たとえば$ 3 \times 5 $の長方形には次のような構成法もあります:

\begin{array}{c} \circ & & \circ & - & \circ & - & \circ & - & \circ \\ | & & | & & & & & & \\ \circ & - & \circ & - & \circ & - & \circ & - & \circ \\ | & & | & & & & | & & \\ \circ & & \circ & & \circ & - & \circ & - & \circ \\ \end{array}

ここで、最初の頂点は最も左の列の真ん中の行に位置しています。