問題です「5チームで総当たり戦。順位をつけてください。」同位は認めません…5チームの「勝敗関係を矢印で向き」をつけたら、一発で明らかになった件
一筆書きの探究から生まれた「超役に立つ」数学！
郵便配達、交通整理、インフラ整備、仕事の割り振り、迷路＆ナンプレ攻略……日常のあらゆるところで応用されている数学「グラフ理論」をご存じでしょうか。データサイエンスや機械学習など、生成AIの基盤となる先端研究にも欠かせない武器となっています。
現代数学の重要テーマであるこのグラフ理論が、豊富な具体例で知識ゼロから理解できる『グラフ理論「超」入門 オイラーの着想から生まれた新しい数学』（講談社ブルーバックス）です。本記事シリーズでは、最短時間で営業ルートをめぐる「巡回セールスマン問題」や、一方通行で事故を減らす「交通整理問題」など、本書で取り上げられている興味深いトピックを厳選してお届けしていきます。
今回は、サッカーなどのチームスポーツでの、総当たり戦の順位づけをグラフを使って考えてみます。
＊本記事は、『グラフ理論「超」入門 オイラーの着想から生まれた新しい数学』（ブルーバックス）を再構成・再編集したものです。
対戦の結果に基づいて、順位をつけよう
さまざまなスポーツでは、対戦の結果に基づいた順位づけを行います。今回は、グラフを使った順位づけをみていきます。
5チームが対戦した結果を順位づけしよう
5チームが対戦した結果が下の表です。
どのように順位をつければよいか考えてみましょう。同位はなく、1から5位までを決めるものとします。
チームABCDE勝負得点失点得失点差A2-15-13-14-140144+10B1-22-34-15-242128+4C1-53-22-11-622714-7D1-31-41-24-323712-5E1-42-56-13-4141214-2
決め方は多数あるので、いくつか紹介しましょう。
「得失点差」を使う
サッカーのリーグ戦などでは多くの場合、勝利と引き分けにポイントを付し、敗戦は0ポイントとして順位づけを行います。この勝敗によるポイントが等しい場合に、得失点差で優劣を決めることになります。
この問題にも、得失点差での順位づけを適用してみましょう。BとCは勝敗が等しいですが、得失点差はBのほうが大きいので、Bを上位とします。DとEも同様に決めると、
1位：A 2位：B 3位：C 4位：E 5位：D
となります。
「直接対決」を利用する
勝敗が等しい場合に、直接対決による結果で順位をつける方法もあります。
この問題の場合は、勝敗の等しいBとCの直接対決を確認すると、CがBに勝っているので上位とします。DとEも同様に決めると、
1位：A 2位：C 3位：B 4位：D 5位：E
となります。
グラフを利用…辺に「向き」をつけて、勝敗をグラフで表す
次に、辺に「向き」をつけて、勝敗をグラフで表すことを考えてみましょう。次図に示すように、勝ったチームから負けたチームに向かう矢印を付すことで「向き」をつけます。
この図のように、すべての辺に向きがついたグラフを「有向グラフ」といい、有向グラフにおける辺を「有向辺」とよびます。
また、各頂点に対して、出ていく有向辺の本数を「出次数」、入ってくる有向辺の本数を「入次数」といいます。
たとえば、頂点vの出次数をod(v)、入次数をid(v)と表します（odとidはそれぞれ、英語の「outdegree」と「indegree」の頭文字を取ったものです）。前図の右に示した各頂点の出次数と入次数を確認してください。
この問題のグラフでは、出次数と入次数の和は「試合数」を表しています。5チームによる総当たり戦なので、どの頂点も両者の和が4になっています。
チーム頂点勝敗有向辺チームの勝ち数出次数チームの負け数入次数
「勝った相手が強かったか」を数値化する
勝敗が一致する場合に「より強い相手に勝ったかどうか」で順位を決めることはできないでしょうか。グラフを用いて順位づけする方法を考えてみましょう。
まず、各チームについて自分たちが勝った相手の出次数の和を求めます。つまり、自分たちから出ていく有向辺の指す先の頂点の出次数の和をとります。
Aから出ていく有向辺の先の頂点はB, C, D, Eなので、2+2+1+1=6です。
Bから出ていく有向辺の先の頂点はD, Eなので、1+1=2です。Cから出ていく有向辺の先の頂点はB, Dなので、2+1=3です。
Dから出ていく有向辺の先の頂点はEのみなので、1です。
Eから出ていく有向辺の先の頂点はCのみなので、2です。
よって、同じ勝敗のBとCではCが上位、DとEではEが上位となり、
1位：A 2位：C 3位：B 4位：E 5位：D
となります。
この図の有向グラフのすべての頂点は、有向辺に沿ってA→C→B→D→Eという順にたどることができます。これに基づいて、順位をつけることが考えられます。
じつは、総当たり戦のどんな結果に対しても、このように辺の向き（有向辺）に沿って進み、すべての頂点を通る経路が存在することが知られています。
以下は、1934年にハンガリーの数学者レーデイによって示されました。
有向ハミルトン道
総当たり戦の勝敗の有向グラフには、向きをたどってすべての頂点を通る経路が存在する。
これに基づいて、勝敗の一部だけを大胆に見た順位づけを『グラフ理論「超」入門』で実際に検証しているので、ぜひご一読ください。
＊
有向グラフを用いると試合の勝敗を表現でき、順位づけにも活用できることがおわかりいただけたかと思います。
次回は、グラフを使って“関係性をもつ人どうしの結びつき”を表す例として「円卓問題」という、興味深い名前のテーマをご紹介しましょう。
グラフ理論「超」入門 オイラーの着想から生まれた新しい数学
一筆書きの数学的探究から生まれた「グラフ理論」。データサイエンスや機械学習に欠かせない重要テーマが、知識ゼロから理解できる！
【続きを読む】「円卓席の最適解」。7人います。3回の席替えで、全員と隣になりたい…これなら実現できる。意外にシンプルな解法と、数学的トリック
