グラフ理論 序説

Takami Torao #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\) がつながっているとき、それらは接続している。

  • 連結グラフ (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) と呼ぶ。

  • 平面的グラフ (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)

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

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

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

  • 最短経路問題 (shortest path problem)

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

    Dijkstra's algorithm

定理

  • 握手補題 (handshaking lemma)

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

  • 隣接行列のべき乗

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

  • オイラーの公式

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

  • 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※1参照。

  • オイラー回路の定理

    連結グラフ \(G\) がオイラー回路を持つための必要十分条件は \(G\) のすべての頂点次数が偶数であること。証明はP.43※1参照。

  • ディラックの定理

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

  • オーレの定理

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

参考文献

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