グラフ理論序説

2018年2月14日 #graphtheory

概要

グラフ理論 (graph theory) は数学的概念であるグラフを説明する理論。問題を頂点と辺からなるグラフに抽象化し、その離散構造そのものを論議の対象とする。

用語

グラフ (graph)

いくつかの頂点と、2つの頂点をつなぐ辺の集合で構成される構造や抽象概念。グラフを構成する頂点集合 $V$ と辺集合 $E$ を合わせて $G = (V, E)$ と表す。
頂点, 節点, ノード, サイト (vertex)

グラフ上で辺を接続することのできる点。頂点の集合を $V = \{v_1, v_2, \ldots\}$ と表す。
辺, リンク, 枝, ボンド (edge, link, branch)

グラフ上の 2 頂点を結ぶ線。頂点 $u$ と $v$ をつなぐ辺を $(u,v)$ と表す。グラフ上の辺の集合を $E = \{(v_1, v_2), (v_1,v_3), \ldots\}$ と表す。
隣接 (adjacency)

2 つの頂点 $v_1$ と $v_2$ が辺でつながっているとき、それらの頂点は隣接である。
接続 (connected)

頂点 $v$ に辺 $e$ がつながっているとき、それらは接続している。

並列辺 (parallel edge)

同じ頂点を結んでいる複数の辺。
自己ループ (self loop)

同じ頂点を結ぶ辺。
単純グラフ (simple graph)

並列辺、自己ループを持たないグラフ。
多重グラフ (multigraph)

並列辺、自己ループを含んだグラフ。

連結グラフ (connected graph)

全体が繋がっているグラフ。つまりグラフ上の任意の 2 頂点 $u$ , $v$ を両端とする道が存在する。
非連結グラフ (disconnected graph)

全体が繋がっていないグラフ。つまりグラフ上のある 2 頂点 $u$ , $v$ を両端とする道が存在しない。
孤立頂点 (isolated vertex)

どの頂点とも隣接していない頂点。
連結成分 (connected component)

グラフ内で連結している単位。

重み付きグラフ (weighted graph)

それぞれの辺が重みの数値を持っているグラフ。単に重み付きグラフと表現した場合は辺重み付きグラフ (edge-weighted -) を指すことが多いが、頂点に重みが付けられている場合は頂点重み付けグラフ (vertex-weighted -) と言う。
有向グラフ (directed graph)

辺が方向性を持つグラフ。有向グラフの辺を有向辺 (directed edge) または弧 (arc) と呼ぶ。
隣接行列 (adjacency matrix)

$n$ 頂点の有限グラフに対して各頂点を行と列に配した $n \times n$ 正方行列。頂点 $v_i$ と $v_j$ が隣接している場合、行列の $(i,j)$ 成分は 1、隣接していない場合 0 となる。重み付きグラフの場合は 1 の代わりに辺が持つ重みを成分とする。

$\left( \begin{array}{cccccc} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \end{array} \right) = \left(\begin{array}{cccccc} (1,1) & (1,2) & (1,3) & (1,4) & (1,5) \\ (2,1) & (2,2) & (2,3) & (2,4) & (2,5) \\ (3,1) & (3,2) & (3,3) & (3,4) & (3,5) \\ (4,1) & (4,2) & (4,3) & (4,4) & (4,5) \\ (5,1) & (5,2) & (5,3) & (5,4) & (5,5) \end{array} \right)$
接続行列 (incidence matrix)

$n$ 頂点 $m$ 辺の有限グラフに対して各頂点を行に、各辺を列に配した $m \times n$ 行列。頂点 $v_i$ と辺 $e_j$ が接続している場合、行列の $(i, j)$ 成分は 1、接続していない場合 0 となる。従って列方向の総和は 2、行方向の総和は頂点 $v_i$ の次数に等しい。

$\left( \begin{array}{cccccc} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 \end{array} \right) = \left(\begin{array}{cccccc} 1a & 1b & 1c & 1d & 1e & 1f \\ 2a & 2b & 2c & 2d & 2e & 2f \\ 3a & 3b & 3c & 3d & 3e & 3f \\ 4a & 4b & 4c & 4d & 4e & 4f \\ 5a & 5b & 5c & 5d & 5e & 5f \\ \end{array} \right)$
隣接リスト (adjacency list)

頂点とそれに隣接する頂点、または接続する辺をリストとして表現したもの。頂点数に対して辺の数が少ない隣接行列は疎行列となるため隣接リストで表現した方が記憶領域の効率が良い。

$\begin{array}{cl} 1 & : 2, 3, 4, 5 \\ 2 & : 1, 5 \\ 3 & : 1, 5 \\ 4 & : 1 \\ 5 & : 1, 2, 3 \end{array}$

次数 (degree)

頂点に接続する辺の数。頂点 $v$ の次数を $d(v)$ と表す。またグラフ $G$ 内で最も大きい次数をそのグラフの次数 $\Delta(G)$ という。
歩道 (walk)

ある頂点から開始し接続している辺と頂点を交互にたどりながらグラフの任意の頂点たどり着く経路。同じ頂点や辺を複数回通過することができる。
小道 (trail)

同じ辺が複数回現れない歩道。頂点は複数回通過してもよい。
道, 路 (path)

同じ頂点を複数回通過しない小道。ただし起点と終点となる頂点は同一でもよい。
回路 (circuit)

起点と終点が同じ小道。
閉路 (cycle)

起点と終点が同じ道。
長さ (length)

歩道に含まれている辺の数。同じ辺であっても通過ごとにカウントする。重み付きグラフの場合は各辺の重みの総和となる。
距離 (distance)

$u$ , $v$ を両端とする道の中で最も短いものの長さ。 $d(u,b)$ で表す。非連結グラフにおいて道が存在しない 2 頂点頂点の距離は無限大 $\infty$ となる。

部分グラフ (subgaph)

グラフ $G'=(V',E')$ のすべての頂点および辺がグラフ $G=(V,E)$ と同一であるとき $G'$ は $G$ の部分グラフという。つまり $V' \in V$ かつ $E' \in E$ が成り立つ。
誘導部分グラフ (induced subgaph)

グラフ $G$ の部分グラフ $G'$ について、全ての頂点 $V'$ が $G$ と同じ辺を持つとき誘導部分グラフである。つまり $E' = \{(u,v)|(u,v) \in E, u \in V', v \in V'\}$ が成り立つ。
補グラフ (complement graph)

グラフ $G$ と同じ頂点 $V$ を持ち、辺の有無が $G$ と逆転しているグラフ。 $\bar{E} = \{(u,v)|u \in V, v \in V, (u,v) \not\in E\}$
同型 (isomorphic)

頂点や辺の識別子を無視すれば本質的に同じ形をしているグラフ。 $G_1$ 上の任意の 2 頂点 $u,v \in V_1$ とその辺 $(u,v)$ に対して、 $G_2$ 上の辺への変換 $(f(u), f(v)) \in E_2$ を満たす単射の $f$ が存在する。このとき $f$ を同型写像 (isomorphism) と呼ぶ。

木 (tree)

閉路を持たない連結グラフ。
森 (forest)

閉路を持たないグラフ。木を連結成分とする非連結グラフ。
葉 (leaf)

木の中で次数 1 の頂点。
根 (root)

木の中で特別な頂点。何が特別かはコンテキストによる。
根付き木 (rooted tree)

根を持つ木。

平面的グラフ (planar graph)

平面上に辺が交差しないように描くことのできるグラフ。実際に平面に描いたグラフを平面グラフと呼ぶ。
2部グラフ (bipartite graph)

グラフ $G$ の頂点集合 $V$ を 2 つの部分集合に分けるとき、すべての辺の両端が 2 つの部分集合のそれぞれに属する頂点を結ぶ (つまり同じ部分集合内の頂点を結ぶことがない) ように分割できるグラフ。
完全2部グラフ (complete bipartite graph)

2部グラフで分けた頂点の部分集合 $V_1$ , $V_2$ のすべての頂点に辺が存在するグラフ。 $|V_1|=n_1$ , $|V_2|=n_2$ のとき完全2部グラフ $G$ を $K_{n_1,n_2}$ と記す。
k-部グラフ (k-partite graph)

頂点集合 $V$ について $1 \leq i \leq k$ , $V_i$ の頂点同士をつなぐ辺が存在しない。頂点数 $n$ のグラフは $n$ 部グラフである。 $k$ 部グラフは $k-1$ 部グラフでもある。
正則グラフ (regular graph)

全ての頂点の次数が等しいグラフ。
k-正則グラフ (k-regular graph)

全ての頂点の次数が $k$ である正則グラフ。頂点数 $n$ の $k$ 正則グラフにおいて次数の総和は $nk$ 、握手定理より辺の数は $\frac{nk}{2}$ となる。
完全グラフ (complete graph, clique)

全ての頂点間に辺が存在するグラフ。頂点数 $n$ の完全グラフを $K_n$ と表す。 $K_n$ は $k-1$ 正則グラフである。 $K_n$ の辺の数は ${}_nC_2 = \frac{n(n-1)}{2}$ である。
次数列

各頂点の次数を降順に並べた数列。ただしグラフには並列辺や自己ループは含まないものとする。ある数列がグラフの次数列となる場合、グラフ化可能列という。握手定理より次数列の総和は偶数となる。

オイラー回路 (Euler circuit)

グラフの各辺を必ず 1 度だけ通る回路a>。すべての頂点の次数が偶数であればグラフはオイラー回路を持つ。頂点を通過するとき、同じ辺を使って戻ることがないことから必ず頂点に接続した 2 本の辺、加えて始点から出発するときに 1 本と終点に到達するときに 1 本を使用する。従って辺の合計数は偶数でなければならず、またすべての頂点の次数は偶数でなければならない。
ハミルトン閉路 (Euler circuit)

グラフの各頂点を必ず 1 度だけ通る閉路。ハミルトン閉路は NP 完全問題である。

モデル問題

最小全域木問題 (MST; minimum spanning tree problem)

頂点と、各頂点の間をつなぐ重み (コスト) 付き辺が定義されている場合に、最も少ないコストですべての頂点をつなげた連結グラフを作成する問題。最小全域木問題参照。
最小シュタイナー木問題 (minimum Steiner tree problem)

グラフ上の頂点集合から任意の部分集合を作成し、その部分集合の頂点の全てを最小のコストでつなぐ問題。NP 困難であることが分かっている。最小シュタイナー問題参照。
最短経路問題 (shortest path problem)

重み付きグラフ上の任意の 2 頂点を結ぶ最も短い経路を求める問題。最短経路問題参照。

定理

握手補題 (handshaking lemma)

全ての頂点の次数の総和は偶数となる。辺 $(u, v)$ の存在は頂点 $u$ と $v$ それぞれに +1 の次数を与え、グラフ全体として +2 の次数を与えているため。
隣接行列のべき乗

重みなし有向/無効グラフ $G$ の隣接行列を $A$ とするとき、その $k$ 回の積 $A^k$ の成分 $(i, j)$ は、 $G$ の頂点 $v_i$ と $v_j$ を両端とする道のうち長さが $k$ となるものの数である。証明はP.11参照。
オイラーの公式

連結な平面グラフの頂点数を $n$ 、辺の数を $m$ 、辺によってできた閉面の数を $k$ とすると $n+k=m+2$ が成り立つ ( $k$ はグラフの外側も 1 と数える)。証明はP.16参照。
Havel-Hakimi の定理

非負整数の降順数列 $(a_1,a_2,\ldots,a_n)$ が単純グラフとしてグラフ可能列であるための必要十分条件は $(a_2-1,a_3-1,\ldots,a_{a_1+1}-1,a_{a_1+2},\ldots,a_n)$ を降順に並べた数列が単純グラフとしてグラフ化可能である。つまり 1)2番目～ $a_1+1$ 番目までの数値を -1、2)先頭の $a_1$ を消す、操作を行った数列がグラフ化可能であること。この操作を再帰的に繰り返すことで最後にすべての次数が 0 になればグラフ化可能列である。証明はP.21参照。
オイラー回路の定理

連結グラフ $G$ がオイラー回路を持つための必要十分条件は $G$ のすべての頂点の次数が偶数であること。証明はP.43参照。
ディラックの定理

$G=(V,E)$ , $|V| \geq 3$ のとき、すべての頂点 $v \in V$ に対して $d(v) \geq \frac{|v|}{2}$ ならば $G$ はハミルトン閉路を持つ。証明はP.46参照。
オーレの定理

$G=(V,E)$ , $|V| \geq 3$ のとき、隣接していない任意の $v$ , $w$ に対して $d(v) + d(w) \geq |v|$ ならば $G$ はハミルトン閉路を持つ。この定理はディラックの定理を真に含んでいる。証明はP.46参照。

参考文献

宮崎修一 "グラフ理論入門基本とアルゴリズム", 森北出版 (2015)
右田正夫,‎ 今野紀雄 "マンガでわかる複雑ネットワーク巨大ネットワークがもつ法則を科学する", SBクリエイティブ (2011)

グラフ理論 序説

概要

用語

グラフ (graph)

頂点, 節点, ノード, サイト (vertex)

辺, リンク, 枝, ボンド (edge, link, branch)

隣接 (adjacency)

接続 (connected)

並列辺 (parallel edge)

自己ループ (self loop)

単純グラフ (simple graph)

多重グラフ (multigraph)

連結グラフ (connected graph)

非連結グラフ (disconnected graph)

孤立頂点 (isolated vertex)

連結成分 (connected component)

重み付きグラフ (weighted graph)

有向グラフ (directed graph)

隣接行列 (adjacency matrix)

接続行列 (incidence matrix)

隣接リスト (adjacency list)

次数 (degree)

歩道 (walk)

小道 (trail)

道, 路 (path)

回路 (circuit)

閉路 (cycle)

長さ (length)

距離 (distance)

部分グラフ (subgaph)

誘導部分グラフ (induced subgaph)

補グラフ (complement graph)

同型 (isomorphic)

木 (tree)

森 (forest)

葉 (leaf)

根 (root)

根付き木 (rooted tree)

平面的グラフ (planar graph)

2部グラフ (bipartite graph)

完全2部グラフ (complete bipartite graph)

k-部グラフ (k-partite graph)

正則グラフ (regular graph)

k-正則グラフ (k-regular graph)

完全グラフ (complete graph, clique)

次数列

オイラー回路 (Euler circuit)

ハミルトン閉路 (Euler circuit)

モデル問題

最小全域木問題 (MST; minimum spanning tree problem)

最小シュタイナー木問題 (minimum Steiner tree problem)

最短経路問題 (shortest path problem)

定理

握手補題 (handshaking lemma)

隣接行列のべき乗

オイラーの公式

Havel-Hakimi の定理

オイラー回路の定理

ディラックの定理

オーレの定理

参考文献

グラフ理論序説