地獄の出張かよ。「最短時間で、5軒は回ってこい」…じつは、そんな「難題がクリアできる、驚きの数学理論」が存在した
一筆書きの探究から生まれた「超役に立つ」数学！
郵便配達、交通整理、インフラ整備、仕事の割り振り、迷路＆ナンプレ攻略……日常のあらゆるところで応用されている数学「グラフ理論」をご存じでしょうか。データサイエンスや機械学習など、生成AIの基盤となる先端研究にも欠かせない武器となっています。
現代数学の重要テーマであるこのグラフ理論が、豊富な具体例で知識ゼロから理解できる『グラフ理論「超」入門 オイラーの着想から生まれた新しい数学』（講談社ブルーバックス）です。本記事シリーズでは、最短時間で営業ルートをめぐる「巡回セールスマン問題」や、一方通行で事故を減らす「交通整理問題」など、本書で取り上げられている興味深いトピックを厳選してお届けしていきます。
まずは、本書の読みどころをご紹介しましょう。
＊本記事は、『グラフ理論「超」入門 オイラーの着想から生まれた新しい数学』（ブルーバックス）を再構成・再編集したものです。
じつは、毎日利用している「グラフ理論」
みなさんは、スマートフォンの地図アプリで「経路検索」をしたことがあるでしょうか。出発地と目的地を入力して検索すると、すぐさま最短の経路が表示され、必要に応じて他のルート候補が複数提案されることもあります。
広大な地図上のどの地点を出発地や目的地に選んでも（それがたとえ国境を越えていても！）、瞬時に最短・最適なルートが表示されるーー考えてみるとすごいことだと思いませんか？
それを可能にしているのが、本書『グラフ理論「超」入門』のテーマである「グラフ理論」です。
グラフと聞くと棒グラフや円グラフ、折れ線グラフを思い浮かべると思いますが、グラフ理論におけるグラフは、これらとはまったく性質が異なります。
点と線の数学
地図の例でいえば、出発地や目的地を「点」、ルートを「線」としてとらえ、「点」を「線」で結んだものがグラフ理論におけるグラフです。このようなグラフを活用することで、複雑な関係性やネットワーク構造を数学的に可視化・モデル化できるのがグラフ理論の強みであり、「点と線の数学」ともよばれる所以（ゆえん）です。
グラフ理論を応用できる対象はじつに幅広く、事故を減らすための交通整理や、水道や電気を効率よく届けるためのインフラ整備に始まり、迷路やナンバープレース（いわゆる“ナンプレ” ）といったゲームの攻略法にまでいたります。
地図を塗り分ける「四色問題」や最短時間で営業ルートをめぐる「巡回セールスマン問題」、ほかにも「美術館問題」や「円卓問題」、「中国人郵便配達問題」など、ユニークな名称をもつ有名問題が多いのもグラフ理論の特徴の一つで、「安定結婚問題」の提唱者にはノーベル賞も贈られています（2012年のノーベル経済学賞）。
グラフ理論はまた、生成AIの基盤として重要なデータサイエンスや機械学習の進化にも大きく貢献しています。情報科学の分野では、線形代数や解析学（微積分）も大切ですが、予備知識を多く必要とする両分野と比べ、視覚的・直感的に理解しやすく、応用範囲のきわめて広いグラフ理論は、日に日に注目度を高めています。
高校数学でも取り上げられるようになってきており、数学オリンピックでもこの分野からたびたび出題されています。
ところで、現代数学において、このように重要な位置を占めるグラフ理論の起源が、「一筆書き」にあるといったら驚くでしょうか？
グラフ理論の起源
『グラフ理論「超」入門』の第6章で紹介するように、
川の両岸と中洲を結ぶ7つの橋を1回だけ渡って、もとの地点に戻ってくることができるか
という難題を、偉大な数学者オイラーは「一筆書きが可能かどうか」というシンプルな問いに置き換えることで解決しました。
この着想が契機となって理論の精緻化が進められ、グラフ理論の現在の隆盛につながっているのです。
1975年に刊行された『グラフ理論入門』（本間龍雄著、講談社ブルーバックス）には、こう書かれています。
グラフ理論は（中略）現代の、あるいは将来の数学の傾向を先取りする数学である。（中略）数学が数や数式のみを扱う学問であった時代はすでに過去のものである。いわゆるグラフが単に数量的関係を図示する手段であったのに対し、グラフ理論のグラフは、もっと質的な関係を表現する機能を持っている。社会も数字万能の時代から、数字で表現できないものを求める時代に移りつつある。数学もそのような時代の要請に答えつつ、しかも数学内部からの必要性に従って新しい時代を迎えつつある。
グラフ理論は、学間的重要さ、応用領域の広さ等の外に、パズル的面白さを十分に持った学問である。
『グラフ理論入門』（本間龍雄著。傍点引用者）
半世紀以上も前に著された先見的な内容に驚かされます。
じつは、同書の刊行時点で、最短経路を求めるアルゴリズムはすでに知られていました。しかし、当時はまだカーナビすら存在しない時代で、時を経てGPSが普及し、いまでは手元のスマホで、行く先々への最短経路を誰でも簡単に調べられるようになったというわけです。
数学が社会に実装された好例であり、同時に、より良い経路をさらに迅速に見出すための数学的アルゴリズムの探究が、いまも継続的に取り組まれています。複雑な関係性を可能なかぎり簡便なグラフで表し、そこに精度の高いアルゴリズムを走らせるーーグラフ理論は、実践的かつ日進月歩の数学なのです。
『グラフ理論「超」入門』は、グラフ理論を予備知識ゼロから理解していただくために書かれました。
前述の有名問題の本質に触れながら、テニス大会での試合の組合せや会食の席決め、仕事の割り振りといった身近な具体例を多数盛り込み、グラフ理論の基本的な考え方に自然に馴染むように構成されています。
多彩なグラフや図を通して、「グラフで表す」「グラフを使う」ことが自然に身につきます。ポイントとなるもの以外は専門用語を用いず、パズル的な面白さも楽しんでいただけるよう工夫しました。
グラフ理論がもつ魅力的な世界を、ぜひ一緒に探訪してみましょう！
＊
では、さっそくグラフ理論がどんなものか、その基本的な考え方がわかる例をご紹介していきましょう。
まずは、「スポーツでの試合の組合せ」を例にご説明します。たとえば、「5人の選手全員が、自分以外の４人と試合をするには、どういう組合わせが考えられるか」という問題で考えてみましょう。
グラフ理論「超」入門 オイラーの着想から生まれた新しい数学
一筆書きの数学的探究から生まれた「グラフ理論」。データサイエンスや機械学習に欠かせない重要テーマが、知識ゼロから理解できる！
【続きを読む】5人がテニスをしようとしています。残念ですが、「全員が3人と対戦する組合せは不可能」です…わかれば、じつに当たりまえ。グラフが示す、その理由
