- 作者: 鈴木晋一
- 出版社/メーカー: 学文社
- 発売日: 2012/03
- メディア: 単行本
- この商品を含むブログ (1件) を見る
本ですが，まえがきによると，高等学校の数学の先生を読者に想定しています．そうすると，「グラフを描き」(p.1)や「G=(V(G),E(G))」(p.2)といった，出だしのところでつまずいたりしないかなんて思ってしまいました．そこをうまく乗り越えられれば，例えば平面グラフを活用して，正多面体が5つに限られることの証明（pp.136-137）は，字数は多いものの，大学入試の数学の答えの書き方に似ているように感じます．
さて本日の本題は，辺彩色です．諸定義と，明らかな性質を確認したのち，次のように書いています．
完全グラフの辺彩色数から調べてみましょう．これによって，スムーズな進行の総当たり戦の組合せを作ることができます．
定理7.11
(1)＝
＝
(2)＝
(p.164)
記号の確認ですが，は，グラフGの辺彩色に必要な色の最小数(p.163)，
は，グラフGの最大次数(p.155)，すなわちある頂点に接続する辺の数の最大値，
は，n頂点完全グラフ(p.9)です．辺彩色とは，グラフのそれぞれの辺に色を割り当てて，隣接するどの2辺も同色にならないようにすること(p.163改)です．総当たり戦との関連は，辺彩色の節の最初(p.162)に，6人の卓球の試合を例にとり説明しています．
定理7.11に戻ります．(1)では，構成的な証明をとっています．
証明．(1) この証明には，回転トリックと呼ばれる方法を利用する．まず，
を次のように描く：2n個の頂点を正(2n-1)角形の頂点v_1, v_2, …*1, v_2n-1とその中心Oにとり，これら2n個の点を線分で結ぶ．このとき，辺Ov_1および直線Ov_1と直交する(n-1)本の辺に色1を塗る．一般に，辺Ov_iおよび直線Ov_iと直交する(n-1)本の辺に色iを塗る(i＝1, 2, …, 2n-1)．(図7.15は，2n＝10の場合を示す．)
(p.164)
(p.165)
本を読み終えて，1日ほど経ってから，気づきました．この回転トリックは，中学の柔道部での，打ち込みの整列と同じなのです．2n＝6の場合で，そのことを確認します．6人にはそれぞれＯ１２３４５とラベルをつけて区別します．まず，次のように並びます．
Ｏ―１ ５―２ ４―３
Ｏすなわちキャプテンの「1本目!」の掛け声で，互いに礼をして，打ち込みをし，終われば礼をします．Ｏは動かず，１２３４５がローテーションします．次の隊形になったら，「2本目!」です．
Ｏ―２ １―３ ５―４
あとは同様です．
Ｏ―３ ２―４ １―５
Ｏ―４ ３―５ ２―１
Ｏ―５ ４―１ ３―２
この次は，初期状態と同じです．
Ｏは１２３４５の順に組みます．他の人は，もちろん順番は違いますが，自分以外と1回ずつ組んでいることが確認できます．「何本目に誰どうしで組むか」は，上記引用の証明の色塗りと，同じ構成となっているのです．
奇数のとき*2は，少しルールが異なります．簡単に言うと，キャプテンも動きます．2n-1＝7の場合を図にします．
Ｏ―１ ６―２ ５―３ （４）
４は，1本目は休みです．1周するまでは，次のようになります．
１―２ Ｏ―３ ６―４ （５）
２―３ １―４ Ｏ―５ （６）
３―４ ２―５ １―６ （Ｏ）
４―５ ３―６ ２―Ｏ （１）
５―６ ４―Ｏ ３―１ （２）
６―Ｏ ５―１ ４―２ （３）
この場合も，各人は，他の人とちょうど1回ずつ組みます．Ｏは１３５休２４６という順番です．7頂点完全グラフの辺の数は21で，1本につき3組が打ち込みをしますので，21÷3＝7となり，7本で1周するというのが最も合理的（6本以下で全員が他の人と組める，そんな組合せは存在しない）なのも確認できます．
途中に「中学の柔道部」と書きましたが，高校のときは，キャプテンの側はみな固定で，反対側の人だけでローテーションしていたように記憶します．
