有向グラフ(directed graph, digraph)
有向グラフ(directed graph) ダイグラフ(digraph)の要素
- 要素が頂点(vertex), 点(point), または節点(node)の集合V
- 弧(arc)と呼ばれる頂点の順序対<始点(initial point), 終点(terminal point)>の集合A
- 多重弧(parallel arc):
- 自己ループ(loop):
- 次数(degree): 頂点vで始まる(begin)弧の本数と終わる(end)弧の本数をそれぞれvの出次数(outdegree)、入次数(indegree)という。
- 入口(source): 入次数が0の頂点
- 出口(sink): 出次数が0の頂点
- 歩道(walk), 小道(trail), 道(path)j, 閉路(cycle): 弧の方向が歩道の方向に一致しなければならないことを除いて無向グラフの場合と同様に定義される。
- 歩道(walk): 頂点と弧の交互列。歩道の弧の数を歩道の長さという。
- 閉じた歩道(closed walk): 同じ頂点を歩道の始点と終点として持つ歩道
- 全域歩道(spanning walk): ダイグラフの全ての頂点を含んでいる歩道
- 小道(trail): 異なる弧をもつ歩道
- 道(path): 異なる頂点をもつ歩道
- 閉路(cycle): 異なる頂点を持つ(始点と終点は除く)閉じた歩道
- 到達可能(reachable): 頂点vから頂点uへの道が存在するときuはvから到達可能という。
- 半歩道(semiwalk), 半小道(semitrail), 半道(semipath): 頂点と弧の交互列において、各弧に対して、の一方が始点で他方が終点であれば、それを半歩道という。半小道、半道についても同様に定義される。
連結性
- 弱連結(weakly connected), 弱(weak): ダイグラフの任意の2頂点u, vの間に半道が存在する
- 片方向連結(unilaterally connected), 方方向(unilateral): ダイグラフの任意の2頂点u, vに対して、uがvに到達可能または、vがuに到達できる(一方の頂点から他方の頂点への道が存在する)
- 強連結(strongly connected), 強(strong): 任意の2頂点u, vに対して、uからvに到達可能かつvからuに到達可能、すなわち、任意の2頂点に双方向の道が存在する
- 強連結→片方向連結→弱連結
- 狭義の片方向(連結)(strictly unilateral): 片方向連結かつ強連結でない
- 狭義の弱(連結)(strictly weak): 弱連結かつ片方向連結でない
Dを有限有向グラフとしたとき
- Dが弱連結⇔Dが全域半歩道を持つ
- Dが片方向連結⇔全域歩道を持つ
- Dが強連結⇔Dと自他全域歩道を持つ
定理:有限ダイグラフが(有向)閉路を含まないとする。このときDは入口と出口を含む。
(証明)
Dが有限なので、長さが最大の道が存在する。それをP=()とする。ここで、終点は出口である。もしそうでなければ、弧()が、Pを拡張する(Pより長い道が存在する)あるいは、なるが存在して閉路を形成する。
同様に、始点は入り口にならなければならない。(証明終わり)
定理:をダイグラフDの行列とする(は弧の数)。このとき、の成分は頂点からに至長さの歩道の個数である。
(証明)
のとき、は弧の個数、すなわち、からへの長さ1の歩道の個数である。したがって、に対して成立している。
とする。このとき、である。
について、(5)が成り立っていると仮定すると、はからへの長さの道の個数である。
また、はからへの弧の個数である。
従って、は、を歩道の最後から2番面目の頂点とするからへの長さの歩道の個数である。故にはからへの長さへの歩道の個数である。
よって、数学的帰納法より(5)が成立する。(証明終わり)
系:個の頂点からなるダイグラフDの行列をとしたとき、
Dが強連結⇔が対角成分以外に0を含まない
(証明)
である必要十分条件は、 ()の成分すべてが0であることである。
これは、からへの長さ以下の歩道が存在しない、すなわち、からへの道が存在しないことを意味する。
よって、(6)が成り立つ(証明終わり)