オムライスの備忘録

数学・統計学・機械学習・プログラミングに関することを記す

トップ > データサイエンス > 【グラフ理論】分野一覧 #まとめ編

【グラフ理論】分野一覧 #まとめ編

データサイエンス

Index

グラフ理論

グラフとは

  • 点 / Vertex / Node
  • 辺 / Edge

によって構成された全体図.

点

点の次数 / Degree

ある点 v に接続している辺の本数 d_{v}.

d_{v}\ =\ deg(v)

次数列 / Degree Sequence

あるグラフ G の点の次数の集合 \{\ d_{n}\ \}_{n=1}^{|V|}.

孤立点 / Isolated Vertex

次数 が 0 の点.

端点 / End Vertex

次数 が 1 の点.

辺

多重辺 / multiple Edge

ある点とある点を結ぶ辺が複数、存在する.

Loop

ある点から出発して、同じ点に到着する辺.

Loop しているある点 v について、 次数の計算を行うときは、その Loop は、2 本として数える.

歩道 (Walk) / 道 (Path) / 閉路 (Cycle)

グラフの種類

単純グラフ vs 一般グラフ

単純グラフ / Simple Graph

多重辺や Loop を含まないグラフ.

一般グラフ / General Graph

多重辺や Loop を許したグラフ.

無向グラフ vs 有向グラフ

無向グラフ / Undirected Graph

ノードが (向きを持たない) エッジで結合されているグラフ.

有向グラフ / Directed Graph

ノードが有向エッジで結合されているグラフ.

オイラーグラフ / ハミルトングラフ.

ラベル付きグラフ / Labeled Graph

ノードラベル付きグラフ

エッジラベル付きグラフ

連結グラフ vs 非連結グラフ

連結グラフ / Connected Graph

どの 2 つの点も辺も道 (Path) で結ばれるグラフ

非連結グラフ / Disconnected Graph

2 つ以上のかたまりからなるグラフ.

木 / Tree

平面的グラフ / Planar Graph

無限グラフ vs 有限グラフ

性質

同形 / Isomorphic

連結性

隣接と接続

隣接 / Adjacent

グラフ G に 2 つの点 v,\ w を結ぶ辺 vw があるとき、 点 v と点 wは、隣接しているという.

点と点の関係



グラフ G の点 v の次数は、 v に接続している辺の本数と同義.

接続 / Incident

上のとき、点 v,\ wは、辺 vw に接続しているという.

点と辺の関係

部分グラフ

行列による表現

隣接行列 / Adjacency Matrix

グラフ G の点が \{1,\ 2,\ \cdots,\ n\} と番号付けされているとする.



G の隣接行列 A とは、点 i と j を結ぶ辺の本数を 行列 A の ij 要素とする n\ \times\ n 行列.

重みなし無向グラフの場合

A\ =\ (a_{ij})

a_{ij}\ =\ \left\{ \begin{array}{ll} 1 & (i,\ j)\ \in\ E \\ 0 & otherwise \end{array} \right.

接続行列 / Incidence Matrix

また、グラフ G の辺が \{1,\ 2,\ \cdots,\ m\} と番号付けされているとする.



G の接続行列 M とは、点 i が、辺 j に接続しているとき、行列 M の ij 要素が 1 であり、 接続していないとき、 0 であるような n\ \times\ m 行列.

次数行列

次数列を対角成分に持つ、対角行列 D.

D\ =\ diag(\ \{d_{n}\ \}_{n=1}^{|V|})

重みなし無向グラフの場合

d_{ij}\ =\ \left\{ \begin{array}{ll} \displaystyle \sum_{k} {a_{ik}} & (i\ =\ j) \\ 0 & otherwise \end{array} \right.

参考

書籍

数理最適化

深層学習

Web サイト