グラフ理論

グラフ理論（グラフりろん、Graph theory）は、数学の一分野。ノード（節点・頂点、英語：node）の集合とエッジ（枝・辺、英語：edge）の集合で構成されるグラフの性質について研究する学問である。なお「エッジ」をリンク（英語：link）という場合もある。

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

グラフとは

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

たとえば、鉄道路線図では駅間の距離や微妙な配置、路線の形状などがしばしば地理上の実際とは異なって描かれている。利用者にとっては駅と駅の「つながり方」が主に重要なのである。

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

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

グラフの例

日常的な問題や工学的問題の多くをグラフとしてみなすことができる。以下はその例である。

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

グラフ理論の起源

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

厳密なグラフの定義

有向グラフ

集合 V , E と、E の元に、二つの V を元の対で対応させる写像

f\colon E\to V\times V

の三つ組

G := (f, V, E)

を有向グラフという。V の元を G の頂点 (vertex) またはノード (node)、E の元を G の辺 (edge) または弧 (arc) と呼ぶ。

無向グラフ

P(V) を V の冪集合とする。E の元に V の部分集合を対応させる写像

g\colon E\to P(V)

があって、E の任意の元 e の像が g(e) = {v₁, v₂} のようにちょうど二つの元の集合になっているとする。このとき、三つ組

G := (g, V, E)

を無向グラフという。V の元を G の頂点、E の元を G の辺と呼ぶ。g の値が常にk > 2個の元の集合となっているとき、k-ハイパーグラフという。

E を最初からある集合の部分集合と考えれば、写像を用いずにグラフを定義することもできる。有向グラフでは、E を V×V の部分集合、無向グラフでは、E を P(V) の部分集合で、二つの元の集合のみからなるものとすればよい。

グラフ理論の用語

頂点と辺

グラフ $G$ の頂点 [英 vertex; pl. vertices] 集合は $V(G)$ 、辺 [英 edge] 集合は $E(G)$ で表す。

重みつきグラフ

グラフの辺に重み（コスト）が付いているグラフを、重み付きグラフ (英 weighted graph)と呼ぶ。乗換案内図の場合、駅間の所要時間が「重み」にあたる。

接合と隣接

辺 $e$ の両端の点を端点 [英 endpoint] といい、端点は辺 $e$ に接合しているという。また、辺と辺がある頂点を共有しているとき、その辺同士は隣接している[英形 adjacent; 名 adjacency]という。

距離と直径

2頂点間の最短経路における辺数を距離 [英 distance ]と呼ぶ。グラフの最大頂点間距離を直径 [英 diameter]と呼ぶ。

ループと多重グラフ

ある辺の両端点が等しいとき、ループ（自己ループ）[英 loop]という。また、2 頂点間に複数の辺があるとき、多重辺 [英 multiedge ?]という。ループも多重辺も含まないグラフのことを単純グラフ [英 simple graph] といい、ループや多重辺を含むグラフのことを多重グラフ[英 multigraph ?]という。

部分グラフと親グラフ

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

次数と正則グラフ

頂点 $v~$ に接続する枝の数を次数といい、 $d(v)$ で表す。有向グラフ [英 directed graph] においては、ある頂点 $v~$ に入ってくる辺数のことを入次数、出て行く辺数のことを出次数という。すべての頂点が同数の隣接点、つまり次数を持つグラフを正則グラフと呼ぶ、 $v$ について、 $d(v)=k~$ が成り立つとき、k -正則という。k-正則なグラフのことをk-正則グラフという。グラフ $G~$ 中の最小次数の頂点の次数を $\delta (G)$ 、最大次数の頂点の次数を $\Delta (G)~$ で表す。また、次数 0 の頂点のことを孤立点という。

通路（ウォーク）と循環（サイクル）

隣接している頂点同士をたどった $v_{1},~e_{1},~v_{2},~e_{2},...,~e_{n-1},~v_{n}$ の系列を歩道（鎖・ウォーク）[英 walk]という。辺の重複を許さない場合、路（小径・トレイル）[英 trail]という。頂点の重複を許さない場合、つまり、両端の2頂点の次数が1、それ以外のすべての頂点の次数が2であるグラフを、道（パス（開いた歩道をパスという場合は単純パス））[英 path]という。また、始点と終点が同じ路のことを閉路（回路・循環・サーキット、サイクル）[英 cycle]、始点と終点が同じ道（つまり $e_{1},~e_{2},~...,~e_{n},~e_{1}$ という路で $e_{i}~$ が相異なるもの）のことを閉道（サイクル）という。

完全グラフとクリーク

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

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

オイラー路（オイラー閉路・オイラーグラフ）
ハミルトン路（ハミルトン閉路・ハミルトングラフ）
木（根つき木・森）
- スパニング木
- シュタイナー木
直径
カット
2部グラフ（n 部グラフ・彩色）
同型グラフ
連結グラフ（連結成分・連結度）
平面グラフ（平面的グラフ）
接続行列・隣接行列
グラフ的な数列
マッチング
閉路グラフ
独立集合

グラフ理論の問題・定理

応用

参考文献

根上生也　『離散構造　情報数学講座3』　共立出版、1993年。
秋山仁・R.L.Graham　『離散数学入門　入門有限・離散の数学1』　朝倉書店、1993年。