グラフ理論のオイラー路とは？
ぐらふりろんのおいらーろ
グラフ理論において、グラフのすべての辺をちょうど1回ずつ通る経路のことで、18世紀の数学者オイラーが「ケーニヒスベルクの橋」問題を解く中で発見した概念です。
グラフ理論のオイラー路（Eulerian path）とは、グラフ（点＝頂点と線＝辺からなる数学的な構造）において、すべての辺をちょうど1回だけ通る経路のことです。出発点と終着点が同じ閉じた経路の場合は「オイラー閉路」（またはオイラー回路）と呼ばれます。
この概念は18世紀のスイスの数学者レオンハルト・オイラーが、プロイセン（現ロシア）の都市ケーニヒスベルクの7本の橋を「すべての橋を1度ずつ渡って元の場所に戻れるか」という問題を数学的に解析したことに由来します。オイラーはこの問題を点と辺によるグラフで抽象化し、グラフ理論の礎を築きました。
オイラー路・オイラー閉路が存在するための条件は明確です。
- オイラー閉路が存在する：グラフが連結で、すべての頂点の次数（辺の本数）が偶数のとき
- オイラー路（閉じていない）が存在する：グラフが連結で、次数が奇数の頂点がちょうど2つのとき（その2頂点が始点と終点になる）
この理論は現代でも実用的な応用があります。たとえば郵便配達のルート最適化（すべての道を1回ずつ通る最短ルートの設計）、回路基板の設計、ゲノム解析におけるDNA配列の再構成などに応用されています。グラフ理論の最重要概念の一つとして、数学・情報科学・工学の幅広い分野で学ばれています。
使い方・例文
数学の授業で「すべての辺を1度ずつ通る一筆書きが可能かどうか」を判定する問題として登場します。また、配送ルートや回路設計の効率化を考えるアルゴリズムの説明にも使われます。
この用語をシェア
最終更新: