home | メインページ

グラフ理論

グラフ理論は、数学の一分野。ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフの性質について研究する学問である。

コンピュータのデータ構造、アルゴリズムなどに広く応用されている。

グラフとは

例えば電車の乗り換え案内図を考える際には、駅（ノード）がどのように路線（エッジ）で結ばれているかが問題であって、線路が具体的にどのような曲線を描いているかは本質的な問題でないことが多い。

事実、乗り換え案内図を書く場合には、駅間の距離や微妙な配置、路線の形状といったものは、地理的な実際のそれとは異なって描かれることが多い。電車で移動する人を対象とした乗り換え案内においては、駅と駅の「つながり方」が主に重要なのである。

このように、「つながり方」に着目して抽象化された「点とそれをむすぶ線」の概念がグラフであり、グラフが持つ様々な性質を探求するのがグラフ理論である。

6 つのノードと 7 つのエッジから成るグラフの一例

つながり方だけではなく「どちらからどちらにつながっているか」をも問題にする場合、エッジに矢印をつける。このようなグラフを有向グラフという。矢印のないグラフは、無向グラフという。

グラフの例

;乗り換え案内図: 前述の通り。 ;電気回路:回路図を書く場合、実際のリード線通りの形状に図を書いたりはしない。この場合も、「接点がどのようにつながれているか」だけが問題であって、「つながり方」を保ちつつできるだけ見やすい形に絵を描く。回路図は一種のグラフである。 ;WWWの構造:WWWにおけるウェブページの、リンク・被リンク関係がなす構造は、有向グラフの一種である。

グラフ理論の起源

グラフ理論は、1736年、「ケーニヒスベルクの問題」に対してオイラーが解法を示したのが起源とされる。この問題は、一筆書きと深く関連している。（詳しくは、一筆書きの項を参照。）

厳密なグラフの定義

有向グラフ

V をノードの集合、E をエッジの集合とする。エッジに二つのノードの対を対応させる関数 f を

とすると、有向グラフ G は

G := (f, V, E)

と定義される。

無向グラフ

P(V) を V のベキ集合とする。エッジにいくつかのノードを対応させる関数 g を

とし、任意のエッジ e に対して g(e) = (v₁, v₂) のように値は二つのノードからなっているとする。この時、無向グラフ G は

G := (g, V, E)

と定義される。g が三つ以上のノードに対応するとき、ハイパーグラフという。

E を最初からある集合の部分集合と考えれば、上の定義から関数を除くこともできる。有向グラフでは、E を V×V の部分集合、無向グラフでは、E を P(V) の部分集合とすればよい。

グラフ理論の用語

グラフの定義によっては、辺に重み（コスト）が付いていることがある。このようなグラフは、重み付きグラフと呼ばれる。

グラフ G の頂点集合は V(G)、枝集合は E(G)で表すことが多い。

辺 e の両端の点を端点といい、端点は e に接合しているという。また、辺と辺がある頂点を共有しているとき、その辺同士は隣接しているという。ある辺の両端点が等しいとき、ループ（自己ループ）という。また、2 頂点間に複数の辺があるとき、多重辺という。ループも多重辺も含まないグラフのことを、単純グラフという。

二つのグラフ G と G' について、G' の頂点集合と辺集合が共に G の頂点集合と辺集合の部分集合になっているとき、G' は G の部分グラフであるという。逆に、G は G' の拡大グラフであるという。特に、頂点集合が等しい部分グラフのことを、全域部分グラフ（生成部分グラフ・因子）という。また、G の頂点集合 V の部分集合 S を取り出して、両端点が S に属する全ての辺を辺集合とする G の部分グラフを、誘導部分グラフという。それから、グラフ G からある辺を取り除き、その辺の両端点を一つの頂点に縮約したとき、縮約グラフ（商グラフ）という。

有向グラフにおいて、ある頂点 v に入ってくる枝の数のことを入次数、出て行く枝の数のことを出次数という。そして、頂点 v に接続する枝の数を次数といい、d(v) で表す。すべての v について、d(v) = k が成り立つとき、 k-正則という。ある k について k-正則なグラフのことを正則グラフという。グラフ G 中の最小次数の頂点の次数を δ(G)、最大次数の頂点の次数を Δ(G) で表すことが多い。また、次数 0 の頂点のことを孤立点という。

隣接している頂点同士をたどった v₁, e₁, v₂, e₂, ..., e_n-1, v_n の系列を歩道（鎖）という。辺の重複を許さない場合、路（小径）といい、頂点の重複も許さない場合、道という。また、始点と終点が同じ路のことを閉路（回路・サイクル）という。

任意の 2 頂点間に枝があるグラフのことを完全グラフ（完備グラフ）という。n 頂点の完全グラフは、K_n で表す。また、完全グラフになる誘導部分グラフのことをクリークという。サイズ n のクリークを含むグラフは「n-クリークである」と言う。辺を持つグラフは必ず 2 頂点の完全グラフを含むので 2-クリークである。また n-クリークであって、直径が n 未満となるグラフを n-クランと言う。

その他のグラフ理論の用語

• オイラー路（オイラー閉路・オイラーグラフ） • ハミルトン路（ハミルトン閉路・ハミルトングラフ） • 木 • 直径 • カット • 2部グラフ（n 部グラフ・彩色） • 同型グラフ • 連結グラフ（連結成分・連結度） • 平面グラフ（平面的グラフ） • 接続行列・隣接行列 • グラフ的な数列

グラフ理論の問題・定理

• 最短経路問題 • ハミルトン閉路問題 • 最小全域木問題 • 最大流最小カット定理 • 四色定理

応用

• デッドロックの検出 • ガベージコレクティング • ファイルシステム • ページランク