Pynote

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

グラフ理論 - グラフ理論の各種用語

グラフの定義及び種類

  • 点 (point)
  • ノード (node)
  • 頂点 (vertex)
  • 辺 (edge)
  • グラフ (graph)
  • 頂点集合 (vetex set)
  • 辺集合 (edge set)
  • 有向グラフ (directed graph)
  • 無向グラフ (indirected graph)
  • 多重辺 (multiple edges)
  • ループ (loop)
  • 単純グラフ (simple graph)
  • 多重グラフ (multigraph)

[定義] グラフ

点 (point)ノード (node) または頂点 (vertex) という要素の有限集合 V と点同士を結ぶ辺 (edge) という要素の有限集合 E から構成される図形のことをグラフ (graph) という。
V頂点集合 (vetex set)E(G)辺集合 (edge set) という。
グラフ G が先に与えられているとき、頂点集合を V(G)、辺集合を E(G) と表すことがある。

[定義] 有向グラフ、無向グラフ

各辺に向きが与えられたグラフを有向グラフ (directed graph)、そうでないグラフを無向グラフ (indirected graph) という。

無向グラフ

有向グラフ

[定義] ループ

同一の点を結ぶ辺をループ (loop) または自己ループ (self loop) という。

例: 辺 \{1, 1\} は端点が同じなのでループである。

[定義] 多重辺

相異なる2点を結ぶ2本以上の辺を多重辺 (multiple edges) という。

例: 点1, 2は2本の辺で結ばれてるので多重辺である。

[定義] 単純グラフ、多重グラフ

多重辺及びループを含まないグラフを単純グラフ (simple graph) という。
多重辺を含むグラフを多重グラフ (multigraph) という。

[定義] 隣接する

  • 接続する (incident)
  • 隣接する (adjacent)
  • 端点 (end point)
  • 端頂点 (end vertex)
  • 近傍 (neighborhood)
  • 接続関数 (incidence function)

点が辺に接続している、点が隣接してる。

e = (u, v) が存在するとき、点 u, v は辺 e接続する (incident) といい、点 u, v隣接する (adjacent) という。
u, v を辺 e端点 (end point) または端頂点 (end vertex) という。
v の隣接点の集合を v近傍 (neighborhood) といい、N(v) または N_G(v) で表す。

辺が点に接続している、辺が隣接している。

e = (u, v) が存在するとき、辺 e は点 u, v接続するという。
e, f が同一の点 v に接続しているとき、ef隣接しているという。

接続関数

辺を引数にとり、その辺が結ぶ点のペアを返す関数を接続関数 (incidence function) という。

[定義] 位数、サイズ

  • 位数 (order)
  • サイズ (size)

グラフ G の点の個数 |V(G)| をグラフ G位数 (order) という。
グラフ G の辺の個数 |E(G)| をグラフ Gサイズ (size) という。
位数 p、サイズ q のグラフを (p, q)-グラフという。

[定義] 次数

  • 次数 (degree)
  • 奇点 (odd vertex)
  • 偶点 (even vertex)
  • 孤立点 (isolated vertex)
  • 端点 (end vertex)
  • 次数列 (degree sequence)
  • 最小次数 (minimum degree)
  • 最大次数 (maximum degree)
  • 平均次数 (average degree)
  • 正則グラフ (regular graph)

ある点に接続している辺の数を次数 (degree) という。点 p の次数を deg(p) と表す。
次数が奇数の点を奇点 (odd vertex)、偶数の点を偶点 (even vertex) という。

点1は辺 (1, 2)、(1, 3) が接続しているので、次数2
点4は辺 (2, 4) が接続しているので、次数4
ループの場合、2とカウントする。

次数0の点、つまり、他のどの点とも隣接していない点を孤立点 (isolated vertex) という。
次数1の点、つまり、1つの辺にのみ接続している点を端点 (end vertex) という。
グラフの次数を増加順に記したものを次数列 (degree sequence) という。

グラフ G最大次数 (maximum degree)\Delta(G)最小次数 (minimum degree)\delta(G) で表す。

すべての点の次数の平均

\displaystyle
ad(G) = \frac{1}{|V(G)|} \sum_{v \in V(G)} deg(v)

をグラフ G平均次数 (average degree) という。

すべての点の次数が同じグラフを正則グラフ (regular graph) という。
正則グラフの各点の次数が r であるとき、そのグラフを r-正則グラフという。

[定義] 同型

  • 同形 (isomorphic)

2つのグラフ G_1 及び G_2 の間に1対1の対応関係があり、G_1 の任意の2点を結ぶ辺の数が G_2 の対応する点を結ぶ辺の数に等しいとき、G_1G_2同形 (isomorphic) であるといい、G_1 \cong G_2 と表す。

\displaystyle
\begin{eqnarray}
\theta: V(G_1) &\to& V(G_2) \\
\phi: E(G_1) &\to& E(G_2)
\end{eqnarray}

が次の関係を満たすことをいう。

\displaystyle
\psi_{G_1}(e) = uv \Leftrightarrow \psi_{G_2}(\phi(e)) = \theta(u) \theta(v)

属性付きのグラフ

  • ラベル付きグラフ (labeled graph)
  • 重み付きグラフ (weighted graph)

各点に名前の付されたグラフをラベル付きグラフ (labeled graph) という。
各辺に重み (weight) の付されたグラフを重み付きグラフ (weighted graph) という。

重み付きグラフの例