【ペア作りシリーズ①】「2人組作って〜」に誰もが安心できるクラスづくり

0. ごあんない

この記事はペア作りシリーズの一番はじめの記事です。
2番目の記事へのリンクはこちら。
mel9.hatenadiary.com

1.「2人組作って～」にビクビクしたくない！

今回は、2人組作って〜と言われたとき、どのような順番で2人組が作られていっても、全員があぶれることなく友達との2人組を組めるような交友関係はどのようなものになるのかを考えます。クラスの人数は偶数とします。

まず思いつくのは全員友達の仲良しクラスの場合です。この場合は誰もが誰とでも2人組を組むことができるので、誰もあぶれることはないですね。平和！

次に、初めから2人組が出来ている場合も考えられます。すなわち、全員友達が1人だけしかおらず、その友達としか2人組を組めないが、友達をほかの人に奪われることもないという状態です。2人組を作るのには適していますが、クラスとして成り立つかどうかには疑問が残る交友関係ですね......

この問いについて詳しくまとめると、

・クラスには偶数人の生徒がいるとする。
・クラス内のどの生徒の組も、友達同士であるか、友達ではないかのいずれかである。
・適当な順番で2人組を作っていく。1人が2つ以上の組に参加してはいけない。
・2人組は友達同士でしか組めない。

このとき、どんな順番で2人組が作られていったとしても、誰一人としてあぶれる人が出ないような交友関係はどのようなものだろうか？

 
という問いになります。

また、このような交友関係を任意2人組づくり可能な交友関係と呼ぶことにします(任意の順番で2人組づくりが可能であるという意味です)。

2.グラフの言葉に落とし込む

交友関係について調べるときは、交友関係をグラフに落とすと考えやすくなります。

たとえば、A,B,C,Dの4人がいて、AとB、AとC、AとD、BとC、CとDが友達であることを図1のグラフで表します。人を点で表し、人と人が友達であることを線で表す感じです。この線のことを辺と呼びます。

図1

なお、このグラフが表す交友関係は、はじめにAとCが2人組を作ってしまった場合にBとDが2人組を組むことができないので、任意2人組作り可能ではありません。

2.1.用語の紹介

ここで、話をしやすくするために、グラフに関する用語を5つ紹介します。
 

連結なグラフ

グラフ上の任意の2点A,Bに対して、辺をたどってAからBまで行く道が存在するとき、そのグラフは連結であるといいます。具体的には、図1のグラフのようにひとかたまりになっているグラフは連結で、図2のグラフのように2つ以上のかたまりに分かれているグラフは非連結です。ここでいう「かたまり」のことをグラフの成分といいます。成分が1つだけなのが連結グラフで、2つ以上あるのが非連結グラフであるともいえます。
連結なグラフは、交友関係でいうと「クラスの誰からスタートしても、友達をたどっていくことで、クラスのすべての人にたどり着くことができる」ことに相当します。

図2

点の次数

点につながっている辺の本数を、その点の次数といいます。図1のグラフではAの次数は3、Bの次数は2です。交友関係でいうと、友達の人数ですね。

図1(再掲)

正則なグラフ

グラフ上のすべての点の次数が等しいグラフを正則なグラフといいます。また、すべての点の次数がkであるとき、そのグラフをk-正則グラフといいます。たとえば、図3のグラフは2-正則グラフです。n人のクラスで全員仲良しの場合、全員が自分以外のn-1人と友達なので、交友関係は(n-1)-正則グラフということになります。

図3

点の除去

グラフの中から1点を選んで、その点とその点につながっている辺をすべて取り除くことを、点を除去するといいます。図2のグラフから点Jを除去すると図4のようになります。

図4

隣接

2つの点同士が辺で結ばれているとき、その2点は隣接していると言います。

2.2.元の問いをグラフの言葉で言うと？

友達同士で2人組を作ることは、グラフの言葉では次の操作に相当します。

操作　辺を1つ選び、その両端点を除去する。

元の問いをグラフの言葉に落とし込むと、次のようになります。

問　Gを偶数個の点を持つグラフとする。グラフに対する操作を次のように定める。

操作　辺を1つ選び、その両端点を除去する。

どのように操作を行ったとしても、全ての点を除去するまで操作を繰り返せるようなグラフGの条件を求めよ。

3.交友関係が連結でない場合

交友関係を表すグラフが連結でない場合について考えましょう。つまり、クラスが2つ以上のグループに完全に分離してしまっている場合を考えます。具体的には図2のグラフのような状況です。

図2(再掲)

このとき、グループαの人とグループβの人の間で2人組が作られることはないので、グループα、βのそれぞれが任意2人組づくり可能であれば、クラス全体が任意2人組づくり可能ということになります。したがって、グラフが非連結の場合は、それぞれのグループについて任意2人組づくり可能かを調べればよいことになります。

よって、ひとまず元の問題に

・交友関係を表すグラフは連結である。

という条件を加えて考えることにします。

問　Gを偶数個の点を持つ連結グラフとする。グラフに対する操作を次のように定める。

操作　辺を1つ選び、その両端点を除去する。

どのように操作を行ったとしても、全ての点を除去するまで操作を繰り返せるようなグラフGの条件を求めよ。

4.交友関係は正則グラフでないといけないらしい

この節がこの記事の核になります。

交友関係が任意2人組作り可能であるためには、交友関係のグラフが正則グラフであることが必要ということが示せます。

定理1
グラフGが連結で任意2人組作り可能であるならば、Gは正則グラフである。

このことを、グラフの点の個数に関する数学的帰納法で示します。つまり、

(I) 非正則で連結な2点のグラフは任意2人組作り可能ではない。

(II)非正則で連結な2k点以下のグラフが任意2人組作り可能ではないならば、非正則で連結な2k+2点のグラフは任意2人組作り可能ではない。

の2つを示すことになります。

(I)は、非正則で連結な2点のグラフは存在しないので真です。

(II)を示すために、次の定理2を示しましょう。

定理2
Gを偶数個の点を持つ非正則連結グラフとする。グラフGに対して、次の操作を行う。
操作　辺を1つ選び、その両端点を除去する。
このとき、うまく辺を選べば、操作後に残るグラフが次の(i)または(ii)を満たすようにできる。

(i) 正則でない成分をもつ。

(ii) 次数0の点をもつ。

4.1.定理2を利用した(II)の証明

定理2より、非正則で連結な2k+2点のグラフに対して、操作後に残る2k点のグラフが(i)または(ii)を満たすような操作を行うことができます。

操作が(i)を満たすときは、操作後に残るグラフのうち正則でない成分は、帰納法の仮定より任意2人組作り可能ではありません。したがって、元の2k+2点のグラフも任意2人組作り可能ではないことになります。操作が(ii)を満たすときは、次数0になった点が必ずあぶれるので、やはり任意2人組作り可能ではありません。

直感的な説明

任意2人組作り可能なためには、残り2人になった時点で図5のようなグラフ(1-正則グラフ)にならなければいけません。しかし、定理2が成り立つならば、最初のグラフが正則でない場合、正則でないことを維持し続けられるような操作が存在することになってしまいます。したがって、元のグラフは正則でなければなりません。

図5

それでは、定理2を示していきましょう。
点の次数の最大値、最小値によって、5通りの場合分けになります。点の個数を2n、点の次数の最大値をt、最小値をsとします。場合分けは
(1) s=1の場合
(2) s=2かつt=2n-1の場合
(3) s=2n-2かつt=2n-1の場合
(4) 3≦s≦2n-3かつt=2n-1の場合
(5) s≧2かつt≦2n-2の場合
の5つです。
・連結　⇒　s≧1
・非正則　⇔　s≠t
であることと、n=1(点の個数が2個)の非正則連結グラフは存在しないので、
・n≧2(点は4個以上)
であることに注意します。

4.2.定理2の証明(1) 最小次数が1の場合

Gは連結なので、次数1の点は次数2以上の点に隣接していなければいけません。もし、次数1の点に隣接しているのが次数1の点だったすると、その2点でグラフが途切れてしまい、連結でなくなってしまうからです。このとき、次数1の点に隣接している点から伸びている辺のうち、次数1の点とを結ぶ辺以外の辺を選んで操作を行えば、次数1の点を孤立させることができます。下の図6でいうと、点A,Bを結ぶ辺を選んで除去すれば良いです。この操作が条件(ii)「操作後のグラフが次数0の点を持つ」を満たす操作になります。
交友関係でいうと、友達が1人しかいない人がいたら、その人を孤立させることができるということになります。厳しいですね。

図6

4.3.定理2の証明(2) 最小次数が2で、最大次数が2n-1の場合

次数が2n-1の点はすべての点と隣接していることがポイントになります。次数2の点に隣接している点のうち、片方は次数2n-1の点ということになります。もう片方を点Aと呼ぶと、次数2n-1の点はこの点Aとも隣接していることになります。ここで、点Aと次数2n-1の点を除去すれば、次数2の点が孤立します。
交友関係でいうと、全員と友達の人がいれば、友達が2人いる人であっても孤立させることができるということになります。2人しかいない友達が早々に2人組を作ってしまったときの絶望感は想像したくないですね。

図7

4.4.定理2の証明(3) 最小次数が2n-2で、最大次数が2n-1の場合

握手補題を利用します。

握手補題
次数が奇数であるような点の個数は偶数個である。

グラフの中で辺が1本増えるごとに、点の次数の総和は2増えます。つまり、次数の総和は必ず偶数でなければいけません。ここで仮にグラフ内に次数が奇数であるような点が奇数個あるとするならば、次数の総和が奇数になってしまいます。したがって、次数が奇数であるような点の個数は必ず偶数個になります。パーティ会場で参加者同士が適当に握手をしたとき、奇数人と握手をした人数は必ず偶数人になっているということです。
このグラフでは点の次数は2n-1または2n-2のどちらかなので、次数が2n-1の点の個数が偶数個であることが言えます。次数が2n-2の点の個数も偶数個です。
ここで、次数2n-2の点が2個の場合と4個以上ある場合で場合分けをします。

4.4.1.次数2n-2の点が2個の場合

次数2n-1の点をどれでもいいから2つ選んで除去する操作が、定理2の条件(i)「操作後のグラフが正則でない成分を持つ」または(ii)「操作後のグラフが孤立点を持つ」を満たす操作になります。n=2なら、次数2n-2(=2)の点がそろって孤立します(図8参照)。n≧3の場合は、次数2n-1の点のうち除去されなかったものは次数が2n-3になり、次数2n-2だった点の次数は2n-4になります。この2点は操作後も隣接しているので、この2点を含む成分が非正則な連結成分になります。

図8

4.4.2.次数2n-2の点が4個以上の場合

この場合、次数2n-2の点同士が隣接している部分が必ずあります。そのような部分に着目しましょう(図9)。図9中の赤い辺(次数2n-1の点と2n-2の点を結ぶ辺)を選んで操作を行います。すると、図中に残された点のうち、次数2n-1だった方は次数2n-3に、次数2n-2だった方は次数2n-4になります。この2点は操作後も隣接しているので、この2点を含む成分が非正則な連結成分になります。

図9

4.5.定理2の証明(4) 最小次数が3以上2n-3以下で、最大次数が2n-1の場合

次数sの点には次数2n-1の点が必ず隣接しています。これとは別に次数sの点に隣接している点を点Aとします。点Aにも次数2n-1の点が隣接していますが、点Aの次数は3以上なので、次数sの点、次数2n-1の点とは別に点Aに隣接している点があります。それを点Bとします。点Bと次数sの点が隣接しているか否かは問いません。ここで点Aと点Bを結ぶ辺を選んで操作を行います。すると、次数2n-1の点の次数は2n-3に、次数sの点の次数はs-1かs-2になります。2n-3>s-1なので、操作後もこの2点の次数は異なります。操作後もこの2点は隣接したままなので、この2点を含む成分が非正則な連結成分になります。

図10

4.6.定理2の証明(5) 最小次数が2以上で、最大次数が2n-2以下の場合

ここが本丸です。ここでは、定理2の対偶となる次の補題1を証明します。

補題1
Gを2n個の点を持つ連結グラフとする。また、Gの全ての点は次数が2以上2n-2以下であるとする。グラフGに対して、次の操作を行う。
操作　辺を1つ選び、その両端点を除去する。
このとき、操作後に残るグラフが次の(i)または(ii)を満たすような辺の選び方が存在しないならば、Gは正則グラフである。
(i) 正則でない成分をもつ。
(ii) 次数0の点をもつ。

方針としては、次数がtの点から出発して、Gのすべての点の次数がtになることを示すことになります。
次数tの点の一つを点Aとします。t≦2n-2より、点Aには隣接していない点があります。これを点Bとします。すると、点Bに隣接している点の次数がtであることが証明できます。これを利用して、点B(点Aに隣接していない点)の次数もtであることが証明できます。最後に、点Aに隣接している点の次数がtで有ることを証明します。グラフ上の点は点Aに隣接しているかしていないかのいずれかであるので、これで証明完了です。

目次
4.6.1. 点Aに隣接していない点に隣接している点の次数はt
4.6.2. 点Aに隣接していない点の次数はt
4.6.3. 点Aに隣接している点の次数はt
4.6.4. 補題1の証明

4.6.1. 点Aに隣接していない点に隣接している点の次数はt

この節では次の補題2を証明します。主張の内容は、補題1の条件下では、最大次数の点に隣接していない点に隣接している点の次数も最大次数になるということです。

補題2
Gを2n個の点を持つ連結グラフとする。また、Gの全ての点は次数が2以上2n-2以下であるとする。Gの最大次数をtとする。グラフGに対して、次の操作を行う。
操作　辺を1つ選び、その両端点を除去する。
このとき、操作後に残るグラフが次の(i)または(ii)を満たすような辺の選び方が存在しないならば、次数tの点に隣接していない点に隣接している点の次数はtである。
(i) 正則でない成分をもつ。
(ii) 次数0の点をもつ。

点Aの次数をtとし、点Bを点Aに隣接していない点とします。グラフは連結なので点Aから点Bに向かう道があります。この道上にあって、点Bに隣接している点を点Cとし、点Cの次数をcとします。図11を参考にしてください。なお、図中の辺ACが緑色になっているのは、点Aと点Cの間に本当に辺があるとは限らないが、点Aから点Cに行く点Bを通らない道があることを表しています。また、破線は隣接していないことを表しています。

図11

ここで、点Bの次数は2以上ですので、点C以外にも点Bに隣接している点があります。その中から1つを選んで点Dとし、点Dの次数をdとします。
ここで辺BDを選んで操作を行うと、操作後にもAとCは同じ成分内にあって、点Aの次数はtかt-1、点Cの次数はc-1かc-2になります。したがって、Aは最大次数の点なので、操作後のグラフが正則でない成分を持たないようにするためには、操作前のグラフはc=tかつ、AとDが隣接しているかつ、CとDが隣接していない状況でなければいけません(図12)。

図12

ここで辺BCを選んで操作を行うと、操作後にもAとDは同じ成分内にあって、点Aの次数はtかt-1、点Dの次数はd-1になります。したがって、操作後のグラフが正則でない成分を持たないようにするためには、操作前のグラフはd=tかつ、AとCが隣接している状況でなければなりません。
A、B、Cを固定して、Bに隣接している点Dの選び方を自由に取り換えて上の議論を続ければ、点Bに隣接している点の次数はすべてtでなければならないことがわかります。

4.6.2. 点Aに隣接していない点の次数はt

上の補題2の証明中で、元のグラフ中で点Cと点Dは隣接していないことが示されました。ここで次数がtである点Cとそれに隣接していない点である点Dに対して補題2を適用すると、点Dに隣接する点Bの次数はtということになります。

4.6.3. 点Aに隣接している点の次数はt

次数がtである点Bとそれに隣接していない点である点Aに対して補題2を適用すると、点Aに隣接する点の次数はtということになります。

4.6.4. 補題1の証明

グラフG上の点は点Aに隣接しているかしていないかのいずれかであるので、4.6.2.および3.節によって、Gのすべての点の次数がtであることが示されました。
したがって、Gは正則グラフです。

以上により、交友関係が任意2人組作り可能であるためには、交友関係のグラフが正則グラフであることが必要であることが示されました！
平和に2人組作りを終えるためには、クラスのみんなが足並みをそろえて友達の人数が同じでなければいけないようです。

5.適切な友達の人数とは？

4節で、任意2人組作り可能なグラフの候補が正則グラフに絞られました。
では、友達の人数は何人であれば良いのでしょうか？
たとえ元の交友関係を表すグラフが正則グラフであったとしても、操作後に残るグラフが(i)「正則でない成分をもつ」または(ii)「次数0の点を持つ」を満たしてしまうことがあるようなグラフでは、2人組を作り終えることができません。つまり、ここで考えなければいけないのは次の問題です。

問　Gを偶数個の点を持つ連結なk-正則グラフとする。グラフに対する操作を次のように定める。

操作　辺を1つ選び、その両端点を除去する。

操作後に残るグラフが次の(i)または(ii)を満たすような辺の選び方が存在しないための、Gの条件を求めよ。
(i) 正則でない成分をもつ。
(ii) 次数0の点をもつ。

 

ここで注意したいのは、操作後に残るグラフの点の次数はk、k-1、k-2のどれかであるということです。除去される点は2つなので、点の次数は高々2までしか減りません。

5.1.操作後のグラフが必ず連結にならなければいけないこと

この節では、操作後に残ったグラフが非連結になったならば、そのグラフは条件(i)「正則でない成分をもつ」または(ii)「次数0の点を持つ」を満たしてしまうことを証明します。
背理法で証明します。操作後のグラフが非連結になり、かつ、そのグラフが条件(i)も(ii)も満たさない(孤立点がなく、操作後のグラフの各成分は正則)と仮定します。操作後のグラフの各成分のうち、少なくとも1点は除去された点の少なくとも一方と隣接していました。したがって、操作後のグラフの各成分が正則な成分であるなら、その成分の各点の次数はk-1かk-2になります。すなわち仮定より、操作後のグラフに次数kの点は存在せず、次数はk-1かk-2のいずれかということになります。
次数k-1の点の個数をm個とします。(k-1)-正則な成分にはk個以上の点が必要なので、m≧kが必要です。同じく、2n-2-m≧k-1が必要です。
ここで、グラフの辺の本数について考察してみましょう。辺が1本増えるごとに次数が2増えるので、グラフの辺の本数は次数の総和÷2です。よって、操作前のグラフの辺の本数は2n×k÷2=nk本です。対して、操作によってなくなる辺の本数は、次のように考えることで、2k-1本であることがわかります。除去される2つの点からはそれぞれk本の辺が伸びているので合計2k本、これでは除去される2つの点同士を結ぶ辺を二重にカウントしてしまっているので1を引いて2k-1本です。したがって、操作後に残るグラフの辺の本数はnk-2k+1本になります。
これを利用して、操作後のグラフの辺の本数に関して式を立てます。

これを解くと、mをnとkで表せます。m≧kと合わせると次のようになります。

同じく、2n-2-m≧k-1を用いると次の不等式が得られます。

この2つの不等式を合わせると、次のような不等式になります

kは正なので、この不等式は偽です。したがって、仮定が誤りで、操作後のグラフが非連結になったならば、そのグラフは条件(i)「正則でない成分をもつ」または(ii)「次数0の点を持つ」を満たします。
この結果は、「グラフが任意2人組作り可能であるためには、操作後のグラフが必ず連結になるようなグラフでなければならない」ことを表しています。また、4節の結果より、任意2人組作り可能なグラフは操作後に残るグラフの連結成分がすべて正則でなければいけませんから、グラフが任意2人組作り可能であるためには、操作後のグラフが必ず連結かつ正則になるようなグラフでなければならないことになります。

5.2.操作後が連結かつ正則グラフになる場合

5.1.節で述べたように、操作後に残るグラフの辺の本数はnk-2k+1です。さらに、操作後に残るグラフは2n-2点の(k-2)-正則連結グラフか(k-1)-正則連結グラフにならなければいけません。ここから、辺の本数に関する式を立てて、kをnで表すと、

ですので、操作後のグラフが(k-2)-正則連結グラフになるにはk=2n-1が必要であり、(k-1)-正則連結グラフになるにはk=nが必要です。すなわち、任意2人組作り可能なグラフの候補は以下の2通りしかないことがわかります。
・(2n-1)-正則グラフで、操作後には必ず(2n-3)-正則連結グラフになる。
・n-正則グラフで、操作後には必ず(n-1)-正則連結グラフになる。

6.候補の絞り込みと十分性の証明

6.1. (2n-1)-正則グラフ

すべての点の次数が2n-1になるためには、すべての点が自分以外のすべての点と隣接していなければいけません。したがって、単に(2n-1)-正則グラフと言っただけで、グラフの形は一意に決まります。この(2n-1)-正則グラフのことを完全グラフと呼びます。交友関係が完全グラフであるということは、みんな友達の平和なクラスであることを意味しているので、当然任意2人組作り可能です。

6.2. n-正則グラフ

(2n-1)-正則グラフの場合と違って、単にn-正則グラフと言ってもグラフの形は一意には決まりません。まず、n-正則グラフで、操作後には必ず(n-1)-正則グラフになるグラフがどのような形のグラフなのか調べましょう。
操作後に残った点の次数がすべて1ずつ減っているということは、操作によって除去された2点の両方に隣接していた点は存在せず、2点のいずれにも隣接していなかった点も存在しません。除去する辺をAB、Aに隣接している点の集合をβ、Bに隣接している点の集合をαとしましょう(図13)。Cをαの元、Dをβの元とします。ここでBCの除去を考えると、操作後のグラフが(n-1)-正則グラフになるためには、Cはβに属するすべての点と隣接していなければならないことがわかります。同じくADの除去を考えると、Dはαに属するすべての点と隣接していなければならないことがわかります。したがって、このグラフはAおよびαに属するすべての点が、Bおよびβに属するすべての点と隣接しており、かつ、Aおよびα内、Bおよびβ内には隣接している点の組み合わせはないようなグラフになります。

図13

このように、点集合を2つに分割して、一方の点集合に属するすべての点からもう一方の点集合に属するすべての点に向かって辺が伸びており、かつ、各集合内の点の間には辺が無いようにできるグラフのことを、完全二部グラフと言います。
n-正則グラフで、操作後には必ず(n-1)-正則グラフになるグラフは、n-正則完全二部グラフでなければいけません。
逆に、n-正則完全二部グラフは任意2人組作り可能であることを説明します。
数学的帰納法を用います。まず、1-正則完全二部グラフは下の図5のようなグラフなので、任意2人組作り可能です。

図5(再掲)

n-正則完全二部グラフの点集合を上の条件を満たすように2つの点集合に分割し、それぞれα、βとします。このグラフに対して操作を行うと、αから1点、βから1点が除去され、残されたグラフは(n-1)-正則完全二部グラフとなります。帰納法の仮定より(n-1)-正則完全二部グラフは任意2人組作り可能であるので、n-正則完全二部グラフもやはり任意2人組作り可能です。

7.交友関係の言葉に戻す

長い道のりでしたが、任意2人組作り可能な連結グラフは完全グラフと正則完全二部グラフの2通りに限られることが示されました！
完全グラフはみんな友達！なクラスです。対して、正則完全二部グラフは全員がクラスの半数と友達ですが、友達の友達は誰一人として友達ではないクラスです。このクラスでは共通の友達を持つ友達は一人もいません。「この前、友達の○○がさ～」って話を振ると、必ず「そいつ友達じゃないわ」と返ってきます。このクラスで3人以上の組を作ろうとすると詰みます。
さて、3節でクラスの交友関係が非連結の場合を除外したのを思い出しましょう。この2通りだけではなく、クラスの交友関係が偶数人の完全グラフや正則完全二部グラフの和になっている場合も、クラス全体が任意2人組作り可能な交友関係になります。というわけで、
誰一人として「2人組作って〜」に怯えることなく過ごすために、クラスの交友関係を完全グラフか正則完全二部グラフ(か、その和)にしましょう！

ここまで閲覧ありがとうございました。

この記事の続きはこちら
mel9.hatenadiary.com