グラフ理論の用語集

Design Structure Matrixを調べているうちに、これの理解にはグラフ理論の勉強が必須と思うようになりましたので以下の本を通読しました。

グラフ理論入門

読んでいる最中に思ったのですがとにかく用語が多い。 そこで今回は上記の本に出てきた用語とその意味を復習しやすいように以下のようにまとめました。内容はほぼその本からの引用になりますが、こちらで多少表現を変えたり説明を加えたりしている部分があります。

グラフ(graph)

点の集合とそれらの結び方の表現。距離的な性質とは無関係。

連結グラフ(connected graph)

どの2点も道で結ばれているグラフ

非連結グラフ(disconnected graph)

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

隣接行列(adjacency matrix)

グラフGの点iとjを結ぶ辺の本数をij要素とするn x n行列

オイラー・グラフ(Eulerian graph)

すべての辺を含む閉じた小道をもつ連結グラフ。またこの小道をオイラー小道という。

半オイラー・グラフ

オイラー・グラフではないが、全ての辺を含む小道があるグラフ

小道

ノードは反復してもよいが辺の反復は許されない道のこと

橋

カットセットが1本のときの辺

ハミルトン閉路

連結グラフGの各点をちょうど一度だけ通る閉じた小道

ハミルトン・グラフ(Hamiltonian graph)

ハミルトン閉路を有するグラフG

半ハミルトン・グラフ

ハミルトングラフではないが、すべての点を通る道があるグラフ

次数

点に接続する辺の数。点vの次数はdeg(v)

単純グラフ

ループも多重辺も含まないグラフ

重みつきグラフ

各辺に非負実数値が割り当てられている連結グラフ

重み

重みつきグラフの各辺に割り当てられた数値のこと。辺eの重みはw(e)で表現する。

林

閉路を含まないグラフ

木

連結な林

全域木

連結グラフGに対して、閉路がなくなるまで1本ずつ辺を除去してできた木

閉路階数

全域木を作成するにあたって除去される辺の数。Gの閉路階数は$\gamma(G)$Gがn個の点とm本の辺とk個の成分からなるとき、$\gamma(G)=m-n+k$

カットセット階数

全域木の辺の本数。$\epsilon(G) = n-k$

深さ優先探索

探索木に使用されるアルゴリズム ネットフローを見つけるために使用される。

幅優先探索

探索木に使用されるアルゴリズム。 最短路アルゴリズムで使用される

欲張り法

最小連結小問題を解くためのアルゴリズム

平面的グラフ

すべての２つの辺が、それらの接続点を除いて幾何学的に交差しないグラフ。またこのような描画を平面描画という。平面的グラフの平面描画を平面グラフと略す。

完全グラフ

任意の2頂点間に辺があるグラフ。n頂点の完全グラフは$K_n$で表す。

完全二部グラフ

２つの頂点集合AとBに対して、Aの各点がBの各点と一本の辺で結ばれているグラフ。A、Bの頂点数をn,mとすると$K_{n,m}$で表す。

位相同形

ある１つのグラフから、その辺に次数２の新しい点をいくつか挿入して得られたグラフ達。

交差数

グラフGを平面に描いたときに生じる交差の最小数。cr(G)

面

平面的グラフGによって分割された平面の領域。非有界な面を無限面と呼ぶ。

グラフの厚さ

いくつかの平面的グラフを重ね合わせてグラフGをつくるときに必要な平面的グラフの最小数。t(G)

k-彩色可能

グラフGの各点にk個の色のうち１つを割り当てて、隣接するどの2点も同じ色にならないようにできること

k-彩色的

Gがk彩色可能であるが(k-1)彩色可能ではないこと。またこのときのGの彩色数をkとして$\chi(G)=k$と書く。

k-(面)彩色可能

隣接する2つの面が同じ色にならないようにk色で面を彩色できること。

k-辺彩色可能

グラフGの隣接する辺が同じ色にならないようにGの辺をk色で彩色できること。

彩色指数

Gがk-辺彩色可能で(k-1)-彩色可能でないとき、kをGの彩色指数として、$\chi'(G)=k$と書く。

彩色関数

Gを単純グラフとし、k色での点彩色の仕方の場合の数$P_G(k)$のこと。

有向グラフ

点集合V(D)と弧集合A(D)からなるグラフD。また弧を辺に置き換えたグラフをDの基礎グラフという。

単純有向グラフ

有向グラフDの弧が全て異なり、かつループがない場合。

Dの隣接行列

Dの点集合を${v1,…,v_n}$として$v_i$から$v_j$へのこの本数を行列成分$a_{ij}$としたn x n行列Aのこと。

強連結

有向グラフDの任意の２点vとwの間にかならずvからwへの道があること。

向きづけ可能

グラフGのすべての辺を方向づけて強連結有向グラフが得られること。

オイラー有向グラフ

連結有向グラフDの全ての弧を含む閉じた小道がある場合。 （矢印を逆流してはいけない）

出次数(out-degree)

有向グラフDのある点vから出発する弧の本数。outdeg(v)。

入次数(in-degree)

有向グラフDのある点vに入る弧の本数。indeg(v)

入口(source)

有向グラフDの点のうち入次数が0の点

出口(sink)

有向グラフDの点のうち出次数が0の点

ハミルトン有向グラフ(Hamiltonian digraph)

有向グラフDのすべての点を含む閉路がある場合

ハミルトン半有向グラフ(semi-Hamiltonian digraph)

ハミルトン有向グラフではないが、有向グラフDにすべての点を通る道があるとき

トーナメント(tournament)

任意の2点がちょうど1本の弧で結ばれている有向グラフ

確率ベクトル(probability vector)

すべての要素が非負で、それらの和が1の行ベクトル

遷移行列(transition probability)

各行が確率ベクトルであるような正方行列

有限マルコフ連鎖(Markov chain)

nxn遷移行列Pと1xn行ベクトルxからなる。

関連有向グラフ(associated digraph)

行列Pの各非零要素を１で置き換えた行列を隣接行列としてもつ有向グラフ

既約連鎖(irreducible chain)

任意の状態から他の任意の状態に移れるマルコフ連鎖のこと。その必要十分条件は、関連有向グラフがが強連結であること。

永続的状態(persistent state)

ある状態$E_i$から出発して、その後$E_i$にやがて戻ってくる確率が1の場合。必要十分条件は、関連グラフに$v_i$から$v_j$に行く道がある場合、その逆もかならずあること。

過渡的(transient)

永続的状態でない場合

吸収状態(absorbing state)

そこから他の状態に行くことができない状態。

周期tの周期状態(periodic of period t)

時間tの整数倍の周期でのみ状態$E_i$に戻る事ができるとき。必要十分条件は、関連有向グラフにおいて$v_i$を含む閉じた小道の長さがすべてtの整数倍であること。

非周期状態(aperiodic state)

周期状態となる周期tが存在しない場合。吸収状態は非周期的状態である。

エルゴード状態(ergodic state)

永続的かつ非周期的である有限マルコフ連鎖の１つの状態

エルゴード連鎖(ergodic chain)

すべての状態がエルゴード的な連鎖

ネットワーク(network)

重み付き有向グラフのこと。

容量(capasity)

ネットワークの各弧aに定められている非負実数$\Psi(a)$

フロー(flow)

ネットワークにおいて各弧aに非負実数$\psi(a)$を割り当てる関数$\psi$のこと。$\psi(a)$は各弧aに対して$\Psi(a)$以下でなくてはならない。また、入口・出口以外の点で出次数と入次数が等しい。この場合に出次数と入次数は、それぞれ流入・流出フローの合計値を指す。

最大フロー(maximum flow)

各点のフローの合計値のうち最大値

カット(cut)

ネットワークの入口・出口をそれぞれv,wとしたときの、vw-非連結化集合

最小カット(minimum cut)

カットの弧の容量の総和のうち最小のもの。

今回はここまでにします。