この地区、一度入ったら出られない…事故が多発しているので、すべての道を一方通行にします。どのように設定したら、よいでしょうか。

2026年4月13日 6時45分

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

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

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

今回は、「交通整理問題」から、一方通行の指定について考えてみます。

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

この地域、すべての道を一方通行にします

グラフ理論の視点を取り入れた交通整理問題として、「一方通行の指定」に挑戦してみましょう。

「一方通行」を指定する

以下に示す地区は道が狭く、事故が多発しているため、すべての道を一方通行にすることを検討しています。

すると、指定地域に住む住民から「すべての道が一方通行になっても、どの地点からどの地点へも行き来できるようにしてほしい」と要望が寄せられました。

そのように一方通行を指定することは可能でしょうか？

グラフを描いてみる

まず、交差点を頂点、道を辺としてグラフを描きます。

一方通行であることを示すために各辺に向きを1つ定め、頂点間を行き来できるようにしましょう。

交差点頂点道辺一方通行辺に向きを与えるどこからどこへも行き来できるどの2頂点を選んでも、

辺の向きに従って行き来できる

「要望に沿った一方通行の指定」ができた！

どの地点からどの地点へも行き来できるような一方通行が指定でき、次図はその一例です。

ただし、うまく一方通行を定めないと、行き来できない地点ができてしまいます。