1998年の東大後期数学のグラフ問題の解答例

はじめに

この記事では,1998年の東京大学後期理科数学の第3問の解答例を紹介します.この問題は大学入試数学の難問として有名です.高校までの数学では習わない「グラフ理論」という分野を題材にした問題です.
この解答は高上の講師のアイデアを清書したものです.

問題

グラフ G=(V,W) とは有限個の頂点の集合 V={P1,…,Pn} とそれらの間を結ぶ辺の集合 W={E1,…,Em} からなる図形とする.各辺 Ej は丁度 2 つの頂点 Pi1, Pi2 (i1≠i2) を持つ.頂点以外での辺同士の交わりは考えない.さらに,各頂点には白か黒の色がついていると仮定する.
例えば,図 1 のグラフは頂点が n=5 個,辺が m=4 個あり,辺 Ei (i=1,…,4) の頂点は Pi と P5 である.P1, P2 は白頂点であり,P3, P4, P5 は黒頂点である.

図1

出発点とするグラフ G1 (図 2) は,n=1, m=0 であり,ただ 1 つの頂点は白頂点であるとする.

図2

与えられたグラフ G=(V,W) から新しいグラフ G′=(V′,W′) を作る 2 種類の操作を以下で定義する.これらの操作では頂点と辺の数がそれぞれ 1 だけ増加する.

(操作 1) この操作は G の頂点 Pi0 を 1 つ選ぶと定まる.V′ は V に新しい頂点 Pn+1 を加えたものとする.W′ は W に新しい辺 Em+1 を加えたものとする.Em+1 の頂点は Pi0 と Pn+1 とし,G′ のそれ以外の辺の頂点は G での対応する辺の頂点と同じとする.G において頂点 Pi0 の色が白又は黒ならば,G′ における色はそれぞれ黒又は白に変化させる.それ以外の頂点の色は変化させない.また Pn+1 は白頂点にする (図 3).

図3

(操作 2) この操作は G の辺の Ej0 を 1 つ選ぶと定まる.V′ は V に新しい頂点 Pn+1 を加えたものとする.W′ は W から Ej0 を取り去り,新しい辺 Em+1, Em+2 を加えたものとする.Ej0 の頂点が Pi1 と Pi2 であるとき,Em+1 の頂点は Pi1 と Pn+1 であり,Em+2 の頂点は Pi2 と Pn+1 であるとする.G′ のそれ以外の辺の頂点は G での対応する辺の頂点と同じとする.G において頂点 Pi1 の色が白又は黒ならば,G′ における色はそれぞれ黒又は白に変化させる.Pi2 についても同様に変化させる.それ以外の頂点の色は変化させない.また Pn+1 は白頂点にする (図 4).

図4

出発点のグラフ G1 にこれらの 2 種類の操作を有限回繰り返し施して得られるグラフを可能グラフと呼ぶことにする.次の問に答えよ.

(1)

図 5 の 3 つのグラフはすべて可能グラフであることを示せ.ここで,すべての頂点の色は白である.

図5

(2)

n を自然数とするとき,n 個の頂点を持つ図 6 のような棒状のグラフが可能グラフになるために n のみたすべき必要十分条件を求めよ.ここで,すべての頂点の色は白である.

図6

解答例

(1)

(1) は操作 1, 2 を使って図 5 のグラフを作るだけです.

~解答

図 5 の左のグラフは,出発点のグラフに対して次の操作を順次適用して得られる (図 a).
1. 頂点 P1 に対して操作 1
2. 頂点 P1 に対して操作 1

図a

図 5 の真ん中のグラフは,左のグラフに対して次の操作を順次適用して得られる (図 b).
1. 頂点 P1 に対して操作 1
2. 頂点 P1 に対して操作 1

図b

図 5 の右のグラフは,出発点のグラフに対して次の操作を順次適用して得られる (図 c).
1. 頂点 P1 に対して操作 1
2. 頂点 P1 に対して操作 1
3. 頂点 P1, P2 の間の辺に対して操作 2
4. 頂点 P4 に対して操作 1
5. 頂点 P4 に対して操作 1
6. 頂点 P2 に対して操作 1
7. 頂点 P2 に対して操作 1

図c

よって,図 5 の 3 つのグラフはすべて可能グラフである.

(2)

(2) の難しいところは,「n 個の頂点の色がすべて白である棒状のグラフが可能グラフならば,n≡0,1mod3」の証明です.n≡0,1mod3 ならば,所望のグラフが可能グラフであることは簡単に示せますが,逆はそうはいきません.
ネット上にある解答では,1 個の白頂点から出発して各操作によって得られるグラフ(可能グラフ)の集合と 1 個の黒頂点から出発して各操作によって得られるグラフの集合を考え,それら二つの集合が交わらないことを不変量を用いて示しています.特に,後者に属する頂点がすべて白の可能グラフの頂点数 n は必ず n≡2mod3 となります.
この記事の解答では,黒頂点に挟まれた白頂点の和を考えています.

~解答

棒状のグラフのみを考える.すべて頂点の色が白のグラフを白グラフとよぶ.頂点数が n のグラフを Gn と書く.出発点のグラフ G1 の唯一の頂点を P1 とおき,Gn に対する操作によって加えられた頂点を Pn+1 とおく.
まず,n≡0,1mod3 ならば,白グラフ Gn は可能グラフであることを示す.
白グラフ Gn が可能グラフならば,白グラフ Gn+3 は可能グラフである.グラフの右端の頂点に対して,操作 1 を 2 回適用し,得られたグラフの右から 2 番目の辺に対して操作 2 を 1 回適用すればよい (図 d).白グラフ G1 が可能グラフであることは明らかである.また,(1) より,白グラフ G3 も可能グラフである.したがって,n≡0,1mod3 ならば,白グラフ Gn は可能グラフである.

図d

次に,白グラフ Gn が可能グラフならば,n≡0,1mod3 であることを示す.グラフ Gk の黒頂点の個数を bk とおき,Gk の両端に黒頂点が加えられたと仮定し(それらは黒頂点の個数には加えない),黒頂点間の白頂点の個数を考える.また,各操作によって G1 から Gk を得るまでに,左端の頂点に対して操作 1 が適用された回数を ℓk とおく.黒頂点間の白頂点の個数それぞれに 1 を加えた数をグラフの左から順に ak,1, ak,2,…, ak,bk+1 とし,

とおく.たとえば,図 e のグラフ G6 において,ℓ6=1 であるとする.

図e

このとき,

であり、

となる.

グラフ Gk から Gk+1 を得る1回の任意の操作において,

または

となる.ここで,−1≡2mod3 より,いずれの場合も

となる.出発点のグラフ G1 から n–1 回の操作によって Gn を得たとき,X1=2, Y1=0 より,

となる.さらに,Gn が白グラフかつ可能グラフならば,

または

である.前者ならば,n≡1mod3, 後者ならば, n≡0mod3 となる.したがって,白グラフ Gn が可能グラフならば,n≡0,1mod3 である.
よって,白グラフ Gn が可能グラフになるために n のみたすべき必要十分条件は

である.(終)

細かい場合分けチェックが大変ですが,グラフと操作の対称性から,操作 1 は右からの操作のみを考えればよいです.左からの操作の回数を考えているのは,単に Xk, Yk を計算するための位置合わせです.Xk–Yk (交代和) で考えてもよいです.

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です