5人がテニスをしようとしています。残念ですが、「全員が3人と対戦する組合せは不可能」です…わかれば、じつに当たりまえ。グラフが示す、その理由

一筆書きの探究から生まれた「超役に立つ」数学！

郵便配達、交通整理、インフラ整備、仕事の割り振り、迷路＆ナンプレ攻略……日常のあらゆるところで応用されている数学「グラフ理論」をご存じでしょうか。データサイエンスや機械学習など、生成AIの基盤となる先端研究にも欠かせない武器となっています。

現代数学の重要テーマであるこのグラフ理論が、豊富な具体例で知識ゼロから理解できる『グラフ理論「超」入門　オイラーの着想から生まれた新しい数学』（講談社ブルーバックス）です。本記事シリーズでは、最短時間で営業ルートをめぐる「巡回セールスマン問題」や、一方通行で事故を減らす「交通整理問題」など、本書で取り上げられている興味深いトピックを厳選してお届けしていきます。

今回は、スポーツなどの試合の組合わせを例に、グラフ理論とはどういうものかをご説明しましょう。

＊本記事は、『グラフ理論「超」入門　オイラーの着想から生まれた新しい数学』（ブルーバックス）を再構成・再編集したものです。

試合の組合わせで考える「グラフ理論」

「グラフ理論」とはなんでしょうか。

その基本的な考え方を知るために、スポーツで「試合を組む」状況を例に、大まかなイメージを掴むところから説明を始めることにしましょう。

卓球やバドミントン、サッカーや野球など、2人あるいは2チームで対戦する形式のスポーツ競技はたくさんあります。ここではテニスを例に、試合の組合せについて考えていきます。なお、同じ人どうしによる対戦は組まない条件とします。

5人（A, B, C, D, E）のプレイヤーがテニスを行う

1. 全員が4人と試合をすることはできるか？　
2. 全員が3人と試合をすることはできるか？　
3. 全員が2人と試合をすることはできるか？

このような問題を逐一、対戦を組みながら考えるのはかなりの手間がかかります。

一方、「グラフ」とよばれる図を使えば、より簡単に解答を得ることができます。では、「グラフ」とはなんでしょうか？

「頂点」、「辺」そして「次数」

グラフ理論における「グラフ」とは、いくつかの「頂点」と、それら頂点を結ぶ「辺」で構成された図のことです。

また、頂点から出ている辺の本数を、その頂点の「次数」といいます。

一般にグラフといえば、xy平面に描かれる直線や曲線のグラフを思い浮かべますが、グラフ理論のグラフは、それら関数のグラフとは異なるため、「離散グラフ」とよばれることもあります。

この問題の場合、5人の「人」を頂点、「試合」を辺、ある人が行う「試合数」を次数として考えます。そして、1.〜3.の各条件でグラフが描ける場合には実際に試合を組むことができ、逆に試合を組むことができるならグラフを描くことができます。

試合の組合せグラフ　　人頂点試合数辺ある人の試合数次数

試合を組める　←→　グラフを描ける

1.から3.の条件で検証してみる

1.は、次図「試合の組合わせを図にする」の左に示したグラフのような試合の組合せが可能です。AとB、AとC、AとD、AとE、BとC、BとD、BとE、CとD、CとE、DとEが対戦し、計10試合が行われます。

この試合数は、辺の本数である10と一致しています。

2.は、後述する理由から、条件に合致する試合の組合せを実現できません。

3.は、次図の中央と右に示したグラフのような試合の組合せが可能です。中央のグラフではAとB、BとC、CとD、DとE、EとAが対戦し、右のグラフではAとB、BとE、EとD、DとC、CとAが試合をし、それぞれ計5試合が行われます。

1.と同様に、この試合数は、辺の本数である5と一致しています。

握手の補題

各頂点から出ている辺の本数＝「次数」についてみてみましょう。

前図「試合の組合わせを図にする」の左に示したグラフではA, B, C, D, E の各頂点の次数は4、中央と右に示したグラフではA, B, C, D, E の各頂点の次数は2となっています。

各グラフの次数の総和を求めてみます。左のグラフでは4×5=20、中央と右のグラフでは2×5=10となっています。

辺の数を2倍すると、次数の総和となっていることにお気づきでしょうか。その理由は、辺は両端で次数として数えられるからです。

これは「握手の補題」とよばれています。風変わりなこの名称は、パーティに参加した人の中で、奇数人と握手した人の人数は必ず偶数になることに由来しています。

握手の補題：奇数人と握手した人の人数は必ず偶数になる

（頂点の次数の総和）=（辺の本数）×2

この定理から、グラフを描くためには、次数の総和が偶数であることが必要であるとわかります。

先ほど、2.の条件に合致する試合の組合せを実現できないといった理由はここにあります。5人全員が3人と試合をすることは、次数が3の頂点を5つもつグラフに対応します。

しかし、この場合は次数の総和が15と奇数となるため、グラフを描くことができません。つまり、5人全員が3人と対戦する試合の組合せは不可能です。

同様の理由から、5人全員が1試合だけ行うこともできません。

また、一般に、偶数人が同じ試合数をしたいときは、1から人数マイナス1のいずれの試合数も可能であり、奇数人が同じ試合数をしたいときは、2から人数マイナス1のうちの偶数の試合数のみ可能です（『グラフ理論「超」入門』で実証しています）。

このようにグラフを用いることで、試合の組合せを図示できます。また、組合せが作れない場合の理由がわかります。

さて、続いては、各プレイヤーの試合数を変えずに組合せを変えることはできるかどうかについて、確かめてみましょう。

5人（A, B, C, D, E）のプレイヤーが

それぞれ、希望の試合数を行う場合

Aは1試合、BとCとEは3試合、Dは2試合をしたいとき、上の図のようなグラフのような組合せを作りました。

ところが、AとEの実力差が大きいので、全員の試合数を変えずに、AとEの対戦がなくなるような組合せに変更したい、ということになりました。そのような変更は可能でしょうか？

　　　＊　　　

次回の解説で、この問題を解いていきます。

グラフ理論「超」入門　オイラーの着想から生まれた新しい数学

一筆書きの数学的探究から生まれた「グラフ理論」。データサイエンスや機械学習に欠かせない重要テーマが、知識ゼロから理解できる！