kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

有向グラフ(directed graph, digraph)

グラフ理論(Graph theory)

有向グラフ(directed graph) ダイグラフ(digraph)の要素

  • 要素が頂点(vertex), 点(point), または節点(node)の集合V
  • 弧(arc)と呼ばれる頂点の順序対<始点(initial point), 終点(terminal point)>の集合A
  • 多重弧(parallel arc): { a_i = < A, B > , a_j = < A, B > }
  • 自己ループ(loop): { a = < A, A > }
  • 次数(degree): 頂点vで始まる(begin)弧の本数と終わる(end)弧の本数をそれぞれvの出次数(outdegree)、入次数(indegree)という。
  • 入口(source): 入次数が0の頂点
  • 出口(sink): 出次数が0の頂点
  • 歩道(walk), 小道(trail), 道(path)j, 閉路(cycle): 弧の方向が歩道の方向に一致しなければならないことを除いて無向グラフの場合と同様に定義される。
    • 歩道(walk): 頂点と弧の交互列。歩道の弧の数を歩道の長さという。 W = (v_0, a_1, v_1, a_2, \cdots , a_n, v_n)
    • 閉じた歩道(closed walk): 同じ頂点を歩道の始点と終点として持つ歩道
    • 全域歩道(spanning walk): ダイグラフの全ての頂点を含んでいる歩道
    • 小道(trail): 異なる弧をもつ歩道
    • 道(path): 異なる頂点をもつ歩道
    • 閉路(cycle): 異なる頂点を持つ(始点と終点は除く)閉じた歩道
    • 到達可能(reachable): 頂点vから頂点uへの道が存在するときuはvから到達可能という。
    • 半歩道(semiwalk), 半小道(semitrail), 半道(semipath): 頂点と弧の交互列において、各弧 a_iに対して、 v_{i-1}, v_iの一方が始点で他方が終点であれば、それを半歩道という。半小道、半道についても同様に定義される。

連結性

  • 弱連結(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が全域半歩道を持つ \cdots (1)
  • Dが片方向連結⇔全域歩道を持つ \cdots (2)
  • Dが強連結⇔Dと自他全域歩道を持つ \cdots (3)


定理:有限ダイグラフが(有向)閉路を含まないとする。このときDは入口と出口を含む。 \cdots (4)
(証明)
Dが有限なので、長さが最大の道が存在する。それをP=( v_i, v_1, \cdots , v_n)とする。ここで、終点 v_nは出口である。もしそうでなければ、弧( v_n, u)が、Pを拡張する(Pより長い道が存在する)あるいは、 u = v_iなる iが存在して閉路を形成する。
同様に、始点 v_0は入り口にならなければならない。(証明終わり)


定理: MをダイグラフDの行列とする({ (m_{i,j}) }は弧{ < v_i, v_j > }の数)。このとき、 M^n i,j成分は頂点 v_iから v_jに至長さ nの歩道の個数である。 cdots (5)
(証明)
 n = 1のとき、 (m_{i,j})は弧{ < v_i, v_j > }の個数、すなわち、 v_iから v_jへの長さ1の歩道の個数である。したがって、 n=1に対して成立している。
 n'>1, M^{n'-1} = (a_{i,k}), M=(b_{k,j}), M^{n'} =(c_{i,j})とする。このとき、 c_{i,j}=\sum_{k=1}^{n'} a_{i,k}b_{k,j}である。

 n=n'-1について、(5)が成り立っていると仮定すると、 a_{i,k} v_iから v_kへの長さ n'-1の道の個数である。
また、 b_{k,j} v_kから v_jへの弧の個数である。
従って、 a_{i,k}b_{k,j}は、 v_kを歩道の最後から2番面目の頂点とする v_iから v_jへの長さ n'の歩道の個数である。故に \sum_{k=1}^{n'}a_{i,k}b_{k,j} v_iから v_jへの長さ n'への歩道の個数である。

よって、数学的帰納法より(5)が成立する。(証明終わり)


系: m個の頂点からなるダイグラフDの行列を Mとしたとき、
Dが強連結⇔ C = \sum_{i=1}^{m-1}が対角成分以外に0を含まない  \cdots (6)
(証明)
 c_{i,j}=0である必要十分条件は、 M^k ( 1\leq k \leq m-1)の (i,j)成分すべてが0であることである。
これは、 v_iから v_jへの長さ m-1以下の歩道が存在しない、すなわち、 v_iから v_jへの道が存在しないことを意味する。
よって、(6)が成り立つ(証明終わり)

有向オイラー

有向グラフにおいて,すべての辺を一度ずつ使用する経路を有向オイラー路という.
s を始点とし,t を終点とするオイラー路が存在するためには

  • すべての頂点の相対出次数が 0 \cdots (7)
  • s の相対出次数が 1, t の相対入次数が 1 で,残りが 0 \cdots (8)

のどちらかであることが必要十分である.
(8)の条件を満たすとき準オイラー路、
(7)の条件を満たすとき,オイラー閉路になる.
オイラー路(Euler Path)