Pynote

Python、機械学習、画像処理について

グラフ理論 - グラフ理論の用語まとめ

部分グラフ、全域部分グラフ、誘導部分グラフ

  • 部分グラフ (subgraph)
  • 全域部分グラフ (spanning subgraph)
  • 誘導部分グラフ (induced subgraph)

グラフ H, G について、E(H) \subset E(G), V(H) \subset V(G) を満たすとき、HG部分グラフ (subgraph) であるという。
特に、V(H) = V(G) のとき、HG全域部分グラフ (spanning subgraph) という。
また、グラフ G から一部の点 V' \subset V(G) を取り出し、V' 上の2点を結んでいる G の辺がすべて含まれているグラフを、V' によって誘導された誘導部分グラフ (induced subgraph) といい、 G[V'] で表す。

V(G): {1, 2, 3, 4}
E(G): {{1, 2}, {1, 3}, {2, 3}, {2, 4}}

例: 全域部分グラフ

V(H): {1, 2, 3, 4}
E(H): {{1, 2}, {2, 3}, {2, 4}}

E(H) \subset E(G), V(H) = V(G) なので、HG の全域部分グラフである。

例: 誘導部分グラフ

V(H): {1, 2, 3}
E(H): {{1, 2}, {1, 3}, {2, 3}}

グラフ HV(H) \subset V(G) で、V(H) 上の2点を結んでいる G の辺がすべて含まれているので、H によって誘導された誘導部分グラフである。

完全グラフ

相異なる2点がすべて隣接している単純グラフを完全グラフ (complete graph) といい、n 点からなる完全グラフを K_n で表す。

例: 完全グラフ K_5

V(G): {0, 1, 2, 3, 4}
E(G): {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}

空グラフ

辺集合が空集合であるグラフを空グラフ (empty graph) といい、N_n で表す。

例: 空グラフ N_3


2部グラフ、n 部グラフ

  • 2部グラフ (bipartite graph, bigraph)
  • 完全2部グラフ (complete bigraph)
  • 星グラフ (star)
  • n 部グラフ (n-partite graph)
  • 完全 n 部グラフ (complete n-partite graph)

グラフ G の点集合を2つの互いに素な集合 V_1, V_2 に分割し、G のすべての辺が V_1 の点と V_2 の点を結ぶようにできるとき、G2部グラフ (bipartite graph, bigraph) という。
V_1 の各点が V_2 のすべての点と隣接している単純な2部グラフを完全2部グラフ (complete bigraph) という。
|V_1| = n, |V_2| = m の完全2部グラフを  K_{n, m} で表す。

例: 完全2部グラフ K_{3, 4}

V(G): {0, 1, 2, 3, 4, 5, 6}
V1: {0, 1, 2}
V2: {3, 4, 5, 6}
E(G): {{0, 3}, {0, 4}, {0, 5}, {0, 6}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {2, 6}}

完全2部グラフ K_{1,n}星グラフ (star) という。

例: 星グラフ K_{1, 5}

V(G): {0, 1, 2, 3, 4, 5}
V1: {0}
V2: {1, 2, 3, 4, 5}
E(G): {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}}

グラフ G の点集合を互いに素な集合 V_1, V_2, \cdots, V_n に分割し、どの辺も両端点が異なる部分集合上にあるとき、Gn 部グラフであるという。
各点が自分が属している部分集合以外のすべての点と隣接しているとき、完全 n 部グラフといい、K_{p_1, p_2, \cdots, p_n}\ \ \ で表す。ただし、|V_i| = p_i, (i = 1, 2, \cdots, n) である。

道、閉路、車輪

  • 道 (path)
  • 閉路 (circuit)
  • 車輪 (wheel)

点集合 {v_1, v_2, \cdots, v_n} と辺集合 \{\{v_i, v_{i + 1}\ \}| i = 1, 2, \cdots, n - 1\} からなるグラフを道 (path) といい、P_n で表す。

例: 道 P_4

V(G): {0, 1, 2, 3}
E(G): {{0, 1}, {1, 2}, {2, 3}}

また、P_n に辺 \{v_n, v_1\}, (n \ge 3) を加えたグラフを閉路 (circuit)といい、C_n で表す。

例: 閉路 C_5

V(G): {0, 1, 2, 3, 4}
E(G): {{0, 1}, {0, 4}, {1, 2}, {2, 3}, {3, 4}}

C_{n - 1} に新しい点 v と辺 \{v, v_i\}, (i = 1, 2, \cdots, n - 1) (n \ge 4) を加えたグラフを車輪 (wheel) といい、W_n で表す。

例: 車輪 W_5

V(G): {0, 1, 2, 3, 4, 5}
E(G): {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {1, 2}, {1, 5}, {2, 3}, {3, 4}, {4, 5}}

補グラフ

  • 補グラフ (complementary graph)
  • 自己補グラフ (self complementary graph)

グラフ G補グラフ (complementary graph) \bar{G} とは、V(\bar{G}) = V(G) であり、2点 u, v\bar{G} で隣接しているのは、u, vG で隣接していないときかつそのときに限るグラフのことをいう。
特に G\bar{G} が同型であるとき、G自己補グラフ (self complementary graph) という。

例: 補グラフ

V(G): {1, 2, 3, 4}
E(G): {{1, 2}, {1, 3}, {2, 4}}

V(C): {1, 2, 3, 4}
E(C): {{1, 4}, {2, 3}, {3, 4}}

G にある辺は C になく、G になかった辺が C にある。
さらに G とその補グラフ C は同型なので、G は自己補グラフでもある。

歩道

  • 歩道 (walk)
  • 長さ (length)
  • 始点 (initial vertex)
  • 終点 (terminal vertex)
  • 小道 (trail)
  • 道 (path)
  • 閉じている (closed)
  • 回路 (cycle)
  • 閉路 (circuit)

グラフ G の点と辺の交互の列 P: v_1 e_1 v_2 e_2 \cdots v_{n - 1} \ e_{n - 1} \ v_n で各辺 e_i が点 v_i, v_{i + 1} に接続している、すなわち、e_i = \{v_i, v_{i + 1}\} となるものを v_1-v_n 歩道 (walk) という。
また、P に含まれる辺の本数を歩道 P長さ (length) という。
v_1 を歩道 P始点 (initial vertex)v_n終点 (terminal vertex) という。

例: 歩道

歩道 P: 0, 1, 4, 6、長さ3、始点0、終点6

同じ辺を含まない、すなわち、e_i \ne e_j, (i \ne j) である歩道を小道 (trail) という。
同じ点を含まない、すなわち、v_i \ne v_j, (i \ne j) である小道を道 (path) という。

歩道 P において、始点と終点が同じ、すなわち、v_1 = v_n であるとき、歩道 P閉じている (closed) という。
閉じた小道は回路 (cycle) といい、閉じた道は閉路 (circuit) という。

例: 閉じている歩道

歩道 P: 0, 1, 4, 3, 0、長さ4、始点0、終点0

連結グラフ

  • 連結している (connected)
  • 連結グラフ (connected graph)
  • 非連結グラフ (disconnected graph)
  • 連結成分 (connected component)
  • 成分 (component)
  • 橋 (bridge)
  • 切断点 (cut point)

グラフ G の2点 u, v の間に u-v 道が存在するとき、2点 u, v連結している (connected) という。
グラフ G のすべての2点が連結しているとき、G は連結している、または G連結グラフ (connected graph) という。
連結していない2点が含まれるグラフを非連結グラフ (disconnected graph) という。

非連結グラフを構成している各連結グラフを連結成分 (connected component) または成分 (component) という。
グラフ G の連結成分の個数を k(G) で表す。
グラフが連結であれば、k(G) = 1 となり、非連結であれば、k(G) \ge 2 となる。

例: 連結グラフ

k(G) = 1

例: 非連結グラフ

k(G) = 2

また、グラフ G の点 v と辺 e に対して、k(G - v) > k(G) となる点 v切断点 (cut point)k(G - e) > k(G) となる辺 e橋 (bridge) という。

例: 切断点

点5を消すと、連結成分の個数が1から2になるので、5は切断点である。

例: 橋

\{0, 5\} を消すと、連結成分の個数が1から2になるので、辺 \{0, 5\} は橋である。


距離、離心数、半径、直径、中心

  • 距離 (distance)
  • 離心数 (eccentricity)
  • 半径 (radius)
  • 直径 (diameter)
  • 中心点 (center point)

グラフ G の2点 u, v に対して、最短の u-v 道の長さを点 uv の間の距離 (distance) といい、d(u, v) で表す。
グラフ G が非連結で、2点 u, vG の異なる成分に属しているとき、u, v の間の距離は d(u, v) = \infty とする。

例: 距離

 1, 5 の距離は、最短の 1-5 道の長さは P: 1, 6, 5 なので、距離は2

連結グラフ G の点 v に対して、v離心数 (eccentricity) e(v)\max_{u \in V(G)} d(u, v) で定める。
この数は v から最も離れた G の点までの距離を示している。

例: 離心数

点1の離心数は、点1から最も離れた点までの距離なので、点4、5の距離2が最大である。よって、点1の離心数は2である。

グラフ G の半径 (radius) を rad(G) = \min_{v \in V(G)} e(v)、直径 (diameter) を diam(G) = \max_{v \in V(G)} e(v) で定める。
半径を与える点、すなわち、e(v) = rad(G) となる点をグラフ G の中心点 (center point) といい、Cen(G) で表す。

例: 半径、直径、中心点

半径: 2
直径: 3
中心: [1, 3, 6, 4]

森、木

  • 森、林 (forest)
  • 木 (tree)
  • 全域木 (spanning tree)
  • 最小全域木 (minimum spanning tree)

閉路を含まないグラフを林または森 (forest) といい、連結な林を木 (tree) という。

例: 森

例: 木

グラフの全域部分グラフで木であるものを全域木 (spanning tree) という。
また、重み付きグラフの全域木の中で最小の重みを持つものを最小全域木 (minimum spanning tree) という。

向きつけ

  • 向きつけ (orientation)
  • 有向道 (directed path)
  • 有向閉路 (directed cycle)
  • 強連結な向きつけ (strongly connected orientation)

グラフの各辺に向きを付けることを、グラフの向き付け (orientation) といい、向き付けられたグラフの u-v 道で、各辺の向きがすべて u から v に向いているものを u-v 有向道 (directed path) という。
また、閉じた有向道を有向閉路 (directed cycle) という。

相異なる2点に対しても一方の点から他方の点への有向道が存在するとき、その向きつけ強連結な向きつけ (strongly connected orientation) という。

有向グラフ

  • 弧 (arc)
  • 弧集合 (arc set)
  • 入次数 (indegree)
  • 出次数 (outdegree)
  • シンク (sink)
  • ソース (source)
  • 弱連結 (weakly connected)
  • 連結 (connected)
  • 片方向連結 (unilaterally connected)
  • 強連結 (strongly connected)
  • オイラー有向回路 (Eulerlian directed circuit)

有向グラフまたはダイグラフ D とは、点という要素からなる空でない集合 V(D) (点集合) と、弧 (arc) という V(D) の要素の順序対の有限集合 A(D) (弧集合 (arc set)) からなるものである。
a = (u, v) が存在するとき、弧 a は点 u を点 v に結ぶといい、u を弧 a の始点、v を終点という。
(u, v)u \to v と表すこともある。

v \in V(D) に対して、点 v を始点とする弧の本数を v出次数 (outdegree) といい、od(v) と表す。
v を終点とする弧の本数を v入次数 (indegree) といい、id(v) と表す。

od(v) = 0 の点をシンク (sink)id(v) = 0 の点をソース (source) という。

u から点 v への有向道が存在するとき、点 u から点 v へ到達可能であるという。

例: 有向グラフ

V(D): {1, 2, 3, 4}
A(D): {(1, 2), (1, 3), (2, 3), (2, 4)}

点2の入次数は od(2) = 1、出次数は od(2) = 2
点1は入次数0なので、ソース、点3, 4は出次数0なのでシンクである。
点1から点4は有向道 P: 1, 2, 4 が存在するので、点1から点4へ到達可能である。

有向グラフ D の弧を向きのない辺に置き換えることによって得られるグラフを基礎グラフまたは底グラフという。

例: 基礎グラフ

V(D): {1, 2, 3, 4}
A(D): {(1, 2), (1, 3), (2, 3), (2, 4)}

辺の向きを無くした基礎グラフは以下である。

V(G): {1, 2, 3, 4}
E(G): {{1, 2}, {1, 3}, {2, 3}, {2, 4}}

基礎グラフが連結のとき、有向グラフ D弱連結 (weakly connected) または連結 (connected) という。
有向グラフ D の任意の2点に対して、少なくとも一方から他方へ到達可能であるとき、片方向連結 (unilaterally connected) といい、共に他方へ到達可能であるとき、強連結 (strongly connected) であるという。

例: 弱連結、強連結

基礎グラフは連結であるから、弱連結である。
3から1への有向道は存在しないので、強連結ではない。

連結な有向グラフのすべての弧を含む閉じた有向小道をオイラー有向回路 (Eulerlian directed circuit) といい、オイラー有向回路を持つ有向グラフをオイラー有向グラフ (Eulerlian directed graph) という。

例: オイラー有向グラフ

V(D): {1, 2, 3}
A(D): {(1, 2), (2, 3), (3, 1)}
オイラー有向回路: [(1, 2), (2, 3), (3, 1)]

有向グラフ D のすべての点を含む有向道を D のハミルトン有向道といい、D のすべての点を含む有向閉路をハミルトン有向閉路という。
ハミルトン有向閉路を持つ有向グラフをハミルトン有向グラフという。

オイラーグラフ

グラフのすべての辺を含む回路をオイラー回路 (Eulerlian circuit) といい、オイラー回路を持つグラフをオイラーグラフ (Eulerlian graph) という。
すべての辺を含む閉じてない小道をオイラー小道 (Eulerlian trail) という。

ハミルトングラフ

  • ハミルトン閉路 (Hamiltonian cycle)
  • ハミルトングラフ (Hamiltonian graph)
  • ハミルトン道 (Hamiltonian path)

グラフのすべての点を含む閉路をハミルトン閉路 (Hamiltonian cycle) といい、ハミルトン閉路を持つグラフをハミルトングラフ (Hamiltonian graph) という。
また、グラフのすべての点を含む道をハミルトン道 (Hamiltonian path) という。