Evolton

東京大学 1998年度 後期日程 第2次学力試験理系(後期)数学 第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は黒頂点である.

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

与えられたグラフ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).

(操作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).

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

問題の図

図1

問題の図

図2

問題の図

図3

問題の図

図4

問題の図

図5  

問題の図

図6

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

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

難易度10/ 10計算量5/ 10目安25分

場合の数、論証・証明 数学的帰納法、偶奇性、必要十分条件、発想重視

方針

(1) 実際の操作列を与える。(2) 十分性はnを3ずつ増やす構成で示す。必要性は、各頂点に0または1を置く連立偶奇条件を定め、2種類の操作の前後で解が一対一に対応する不変量を作る。

解答

(1)
3頂点の棒状グラフは、最初の白頂点に操作1を2回続けて施せば得られる。最初の頂点は2回色が反転して白に戻り、新しい2頂点も白である。

4本の葉を持つ星形グラフは、最初の白頂点に操作1を4回施せば得られる。中心は4回反転して白、4個の葉はすべて白である。

最後のグラフは次のように作れる。まず操作1で黒頂点と白頂点を結ぶ。白頂点に操作1を3回施すと、その頂点には白い葉が3本付き、中心と最初の頂点はともに黒になる。この2黒頂点を結ぶ辺に操作2を施すと、両者は白になり、間に白頂点が入る。最後にこの新しい白頂点に操作1を2回施す。すると2つの白い4価頂点が結ばれ、各々に白い葉が3本付いた所要のグラフになる。

(2)

まず十分性を示す。
n=1は出発グラフであり、n=3は(1)で構成した。全白の棒状グラフCkが可能だとする。その端の白頂点に操作1を施し、次に新しくできた端の白頂点に操作1を施す。端には⋯−黒−黒−白が並ぶ。2個の黒頂点を結ぶ辺に操作2を施せば、4頂点とも白の棒⋯−白−白−白−白となり、頂点数は3増える。従ってn≡0,1(mod3)ならばCnは可能である。

(2) 必要性
各頂点vに数xv∈{0,1}を対応させ、各頂点でεvxv+∑w: w は v と隣接xw≡0(mod2)を課す。ただしvが白ならεv=1、黒ならεv=0とする。

操作1で頂点vに白い新頂点zを加えると、新頂点の式はxz+xv≡0,すなわちxz=xvである。これを色が反転したvの式に代入すると、反転で増減したxvとxzが打ち消し合い、操作前のvの式に戻る。従って操作前後の解は一対一に対応する。

操作2で辺uvを白い新頂点zで2分すると、新頂点の式はxz+xu+xv≡0,すなわちxz=xu+xvである。これを色が反転したu,vの式に代入すると、それぞれ操作前の式に戻る。従ってこの操作でも解は一対一に対応する。

出発グラフでは式はx1=0であり、解は零解だけである。従って可能グラフでは上の連立条件に非零解は存在しない。

ところが、全白の棒状グラフでn=3m+2なら、左から1,1,0,1,1,0,…,1,1と周期3でxvを置くと非零解になる。実際、内部では連続する3項の和が偶数で、両端でも隣り合う2項の和が偶数である。これは可能グラフには非零解がないことに反する。

従ってn≢2(mod3)が必要である。十分性と合わせてn≡0 または 1(mod3)が必要十分条件である。

別解

解法2(許容する0・1印の個数を不変量にする)

方針

(1) は操作列を簡潔に指定する。(2) は各頂点へ0・1の印を置く規則を定め、その許容配置の個数が2種類の操作で変わらないことを示す。全白の棒では印が周期3で伝わるため、許容配置が1個になる長さを判定する。

解答

(1)
3頂点の棒は、出発頂点に操作1を2回施せば得られる。4本の葉を持つ星は、出発頂点に操作1を4回施せば得られる。

3つ目のグラフは次の順に作る。まず出発頂点 A に操作1を施して白い頂点 B を加える。B に操作1を3回施すと、B に白い葉が3本付き、A,B は黒になる。辺 AB に操作2を施して間に白い頂点 C を入れると、A,B は白へ戻る。最後に C に操作1を2回施す。すると B,C が隣接する2つの4価頂点となり、各々に白い葉が3本付く。

(2)
まず構成を示す。n=1,3 の全白の棒は可能である。全白の n 頂点の棒の端に操作1を2回施すと、端に黒、黒、白の3頂点が続く。このうち黒と黒を結ぶ辺に操作2を施せば全部白となり、頂点数が3増える。従ってn≡0, 1(mod3)なら構成できる。

次に必要性を示す。各頂点 v に xv=0 または1の印を置き、次の条件を課す。εvxv+∑w: w は v の隣xw≡0(mod2),ただし v が白なら εv=1、黒なら0とする。この条件を満たす印の置き方を許容配置と呼ぶ。

操作1で新頂点 z を加えると、z の条件から xz=xv と一意に決まる。これを色が反転した v の条件へ戻すと、操作前の条件に一致する。操作2でも新頂点の条件xz=xu+xvから新しい印が一意に決まり、両端の条件は操作前へ戻る。従って許容配置の個数はどちらの操作でも変わらない。出発グラフでは零配置の1個だけだから、可能グラフの許容配置も1個だけである。

全白の n 頂点の棒で、左端の印を t とする。左端条件から次の印も t、内部条件から印はt,t,0,t,t,0,…と周期3で伝わる。右端条件まで自動的に満たされるのは n≡2(mod3) のときであり、この場合は t=0,1 の2配置がある。これは可能グラフの許容配置が1個であることに反する。

従って必要十分条件はn≡0 または 1(mod3)である。

総評

難度10、計算量5。必要性が本問の核心である。一般の行列式やグラフ理論の定理は使わず、0・1の連立偶奇条件を各操作で直接追跡して不変性を証明した。構成側と不可能性側の両方を完結させた。 2解法の数式と最終結論を相互照合し、原典本文との対応、小問の完答、境界条件、図の読み取りを再確認した。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る東大の場合の数の問題で問題集を作る

出典: 東京大学 1998年度 後期 理科 第3問。問題文はHTML表示のために再入力・数式組版しています。