グラフ理論

グラフ理論（graph theory）は、頂点とそれらを結ぶ辺からなるグラフを研究する離散数学の分野である。

グラフ

交通網、通信網、人間関係などは、対象を頂点、関係を辺として表現できる。辺に向きや重みを持たせる場合もある。

代表的な問題

最短路、巡回路、彩色、連結性、最大流などが代表的なテーマである。アルゴリズムやネットワーク設計とも密接に関係する。

応用

コンピュータ科学、物流、ソーシャルネットワーク、生物学、回路設計などで利用される。

頂点の次数と握手補題

無向グラフで頂点につながる辺の本数を次数という。各辺は両端で一度ずつ数えられるので、全頂点の次数の和は辺数の2倍となる。自己ループは次数に2として数える。この和は偶数だから、奇数次数の頂点の個数も偶数でなければならない。局所的な接続数から全体への制約が得られる。

例：一筆書きできる条件

辺を一度ずつ通るオイラー路を考える。途中で通過する頂点では入る辺と出る辺が対になるため、始点と終点以外の次数は偶数になる。辺を持つ部分が連結なら、奇数次数の頂点が0個または2個であることが一筆書きの必要十分条件となる。0個なら出発点へ戻る閉路を作れる。

木・最短路・巡回路の違い

連結で閉路のないグラフを木といい、頂点がn個なら辺はn−1本である。木では二頂点を結ぶ単純な道が一つしかない。重みのない最短路は幅優先探索、非負の重み付き最短路はダイクストラ法が代表的な方法となる。一方、頂点を一度ずつ巡るハミルトン路は辺を巡るオイラー路とは別問題で、同じ次数条件だけでは判定できない。

関連項目