グラフ、次数、オイラー路
定義と範囲 事実
有限無向多重グラフ G=(V,E) は、頂点の有限集合 V と辺の有限集合 E からなる。各辺は、たどる向きを指定せずに二つの頂点を結ぶ。同じ頂点対を複数の辺が結ぶこともあり、ループが一つの頂点をその頂点自身に結ぶこともある。単純グラフは、ループも平行辺もない特殊な場合である。
この枠組みを選ぶのは、ケーニヒスベルクでは複数の橋が同じ陸地どうしを結んでおり、それを表すには平行辺が必要だからである。本稿では、辺に向きがある有向グラフも、辺が距離やコストなどを持つ重み付きグラフも扱わない。
したがって、基礎となる多重グラフが保持するのは接続関係、すなわち各辺がどの頂点を結ぶかだけである。図に描かれた位置、長さ、角度は定義に含まれない。これらのデータは有用な場合にはモデルに加えられるが、ここで扱う問題には必要ない。
最小限の用語 事実
| 用語 | 無向多重グラフにおける定義 |
|---|---|
| 頂点の次数 | 頂点に接続する辺の端点の数; ループは2と数える |
| 歩道 | 接続する頂点と辺の列; 頂点と辺は繰り返してよい |
| 小道 | どの辺も繰り返さない歩道 |
| 道 | どの頂点も繰り返さない歩道 |
| 回路 | 閉じた小道: 出発点と到着点が一致する |
| 閉路 | 共通の出発点兼到着点を除き、どの頂点も繰り返さない回路 |
| 連結 | 任意の頂点対を道が結ぶ |
オイラー路は各辺をちょうど一度ずつ使う。両端が異なれば開いており、出発頂点に戻ればオイラー回路となる。ここで「オイラー」という語が対象とするのは辺であり、頂点ではない。
握手補題 事実
通常の各辺には二つの端点があり、その両頂点の次数にそれぞれ1を加える。ループにも二つの端点があり、どちらも同じ頂点にあるため、その次数に2を加える。多重度を含めて数えると、各辺は総和にちょうど2ずつ寄与する:
v∈V∑deg(v)=2∣E∣
右辺は偶数である。偶数次数の頂点が寄与する和は偶数なので、奇数次数の総和も偶数でなければならない。奇数の整数の和が偶数になるのは、項の数が偶数である場合に限る。したがって、奇数次数の頂点は常に偶数個ある。
集会を表す単純グラフでは、辺は二人が握手したことを意味する。このとき補題は、奇数回握手した人の数が偶数であると述べる。このイメージが名称の由来だが、先の次数の規約を用いれば、証明は多重グラフとループにも成り立つ。
ケーニヒスベルクの橋 事実
歴史的な問題は、七本の橋で結ばれた四つの陸地を扱う。問われたのは、出発点に戻ることを要求せず、各橋をちょうど一度ずつ渡る散策を見つけることだった。
オイラーは陸地を文字で表し、連続する横断を文字列で記した。現代のグラフ理論による定式化では、各陸地が頂点に、各橋が辺になる。得られる多重グラフには、次数が5、3、3、3の四つの頂点がある。その和は14で、辺の本数である七の二倍となり、補題と一致する。
オイラー路では、接続するすべての辺が使われる。中間頂点を通過するたび、辺は対で消費される。一本で入り、一本で出るからである。したがって、開いたオイラー路では出発点と到着点だけが奇数次数となり、オイラー回路には奇数次数の頂点が一つもない。
ケーニヒスベルクにはそれが四つある。七本の橋をそれぞれちょうど一度ずつ使う小道は存在しない。 オイラーはこの不可能性を証明し、一般的な偶奇の規則を定式化した。現代の定理は完全な特徴づけを与える。
現代のオイラー定理 事実
次数が零でないすべての頂点が同じ連結成分に属する有限無向多重グラフを考える。
- すべての頂点の次数が偶数である場合、かつその場合に限り、オイラー回路を持つ。
- ちょうど二つの頂点の次数が奇数である場合、かつその場合に限り、開いたオイラー路を持つ。その二つが必ず出発点と到着点になる。
必要性は、入る辺と出る辺の対から導かれる。十分性は構成的に示せる。すべての次数が偶数なら、辺に接続する頂点から出発し、まだ使っていない辺をたどる。別の頂点で行き止まりにはならない。そこへ到着するたび、偶奇性により、出発に使える未使用の辺が残るからである。したがって、小道は最終的に出発点へ戻り、回路を形成する。
辺が残っている場合、連結性により、回路上のある頂点がまだ使われていない部分に接していることが保証される。その頂点から新しい回路を作り、最初の回路に挿入する。この操作を繰り返すと、すべての辺を含む回路が得られる。これが Hierholzer のアルゴリズムの原理である。
奇数次数の頂点がちょうど二つある場合、その間に一時的に辺を一本加える。すべての次数が偶数になるので、オイラー回路を構成してから、追加した辺を取り除く。すると回路は開き、その両端がまさに二つの奇数次数の頂点である小道になる。
モデル化には適切な構造の選択が必要 事実
道路、ソフトウェアの依存関係、分子、電気回路はいずれもグラフで表現できるが、条件を明確にせず同じモデルを使うことはできない。
- 道路網は無向の場合も有向の場合もあり、多くは距離や移動時間を持つ。
- 依存関係グラフは一般に有向であり、そこでの閉路は循環依存を表す。
- 分子グラフでは、原子と結合にラベルが付く。
- 電気回路網には、接続関係だけには含まれない物理量と法則が加わる。
したがって、抽象化の利点は、一つのアルゴリズムがあらゆる場面に適用できることではない。共通構造である頂点と辺を分野固有の情報から分離し、構築したグラフに仮定が正確に一致する定理またはアルゴリズムを選べることにある。
まとめ
辺が同じ連結成分に属する有限無向多重グラフでは、各辺をちょうど一度ずつたどれるかどうかは次数の偶奇で決まる。奇数次数の頂点がゼロなら回路、ちょうど二つなら開いたオイラー路が存在する。