# 有向グラフ ## 定義 有向グラフ(directed graph、略して digraph)`G` は、頂点(vertex、node とも呼ぶ)の集合 `V(G)` と有向辺(directed edge、arrow とも呼ぶ)の集合 `E(G)` からなる構造である。各有向辺は始点である尾(tail)頂点 `u` から終点である頭(head)頂点 `v` へ向かい、順序対 `(u,v)` として表され `⟨u→v⟩` と書く。有向グラフは、頂点集合を定義域・余域とする**二項関係と形式的に同一の対象**である——すなわち、有向グラフの辺集合は、定義域と余域が同じ集合であるような二項関係の「グラフ(graph、値の組の集合という意味での)」にほかならない。この対応により、[[二項関係]]で定義された合成・逆関係・恒等関係などの操作がそのまま有向グラフに適用できる。頂点の入次数(in-degree)は入辺の本数、出次数(out-degree)は出辺の本数であり、有限有向グラフでは全頂点の入次数の総和と出次数の総和はいずれも辺数に等しい(Handshaking Lemma)。頂点と辺が交互に並ぶ有限列を歩道(walk)、同じ頂点を二度訪れない歩道を道(path)、始点と終点が一致する歩道を閉歩道(closed walk)、正の長さを持ち始点=終点を除いて頂点が相異なる閉歩道を閉路(cycle)と呼ぶ。n頂点の有向グラフはn×nの隣接行列(adjacency matrix)`A_G` で表現でき、`A_G` のk乗の(i,j)成分は頂点iからjへの長さkの歩道の本数に一致する。閉路を持たない有向グラフをDAG(有向非巡回グラフ、directed acyclic graph)と呼び、DAG はスケジューリング問題([[トポロジカルソート]])や、推移的かつ非反射的な関係([[半順序]])の描像として中心的な役割を果たす。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]]) ## 横断的知見 - 第4章は二項関係を「定義域A・余域B・A×Bの部分集合であるグラフ」の三つ組として先に定義し、その時点では有向グラフへの言及は予告にとどめていた([[二項関係]]参照)。第9章はこの予告を回収し、「有向グラフ=定義域と余域が同じ集合である二項関係」という等式を明示する。両章を並べると、有向グラフは新しい構造ではなく、二項関係のうち定義域と余域が一致する特別な場合の**別名(視点の変更)**にすぎないことが分かる。矢印本数条件による5性質(関数・全域・全射・単射・全単射、[[二項関係]]参照)は有向グラフの語彙では「各頂点の出次数・入次数の上限/下限」として読み替えられる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]], [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]]) - 第11章冒頭は単純グラフ([[単純グラフ]])を「辺が向きを持たない有向グラフ」と直感的に導入するが、その直後の形式的な定義(Definition 11.1.1)は有向辺の集合を無向化する操作としてではなく、辺を最初から2元集合 `{u,v}` として独立に公理化し直している。つまり単純グラフは有向グラフの商構造(向きを捨てる同値関係による商)として定義されているのではなく、平行した独立の構造である。この違いは閉路の定義にも表れる: 有向グラフでは長さ2の閉歩道 `u→v→u` も閉路になりうるが、単純グラフでは同じ辺を往復する長さ2の閉歩道が常に存在してしまうため閉路に含めず、長さ3以上に規約を変えている。したがって「有向グラフの辺を無向化すれば単純グラフが得られる」という素朴な対応づけは、閉路・歩道の数え上げに関しては成り立たない点に注意が必要である。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]], [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]]) - 第9章は有向グラフを「歩道・道・閉路・隣接行列」という**静的な構造**として導入するのに対し、第20章はその同じ構造の上に**確率過程(ランダムウォーク)**を重ね、辺に遷移確率を割り当てることで有向グラフを動的なモデルへ拡張する。具体的には、第20章はWebページを頂点、ハイパーリンクを有向辺とする有向グラフを、各頂点 `x` の出辺に一様な遷移確率 `1/outdeg(x)` を割り当てることでランダムウォークの土台とし、[[PageRank]] をこのウォークの[[定常分布]]として定義する。第9章の隣接行列 `A_G` のk乗が「長さkの歩道の本数」を数えるのに対し、第20章の(遷移確率で重み付けした)隣接行列のk乗は「kステップ後に各頂点にいる確率」を与える——両者は同じ行列べき乗という操作でありながら、数え上げ(組合せ論)と確率(測度)という異なる解釈を与える点で対照的である。さらに第9章のDAG(有向非巡回グラフ)は半順序の描像として使われたが、第20章が定常分布の一意性条件として要求する**強連結性**はDAGとは正反対の性質(DAGは非巡回ゆえ強連結になり得ない)であり、有向グラフの2つの重要な特殊構造(DAGと強連結グラフ)が、それぞれ異なる下流の応用(スケジューリング/半順序 vs ランダムウォークの収束保証)に対応していることが分かる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]], [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] §20.2.2-§20.2.3) ## 未解決の問い - 第10章(通信ネットワーク)・第12章(平面グラフ)は、それぞれ有向グラフの特殊化(有向辺に容量を付けた通信網)や関連構造を扱う予定である。 - 隣接行列によるk乗と歩道数え上げの対応(定理9.3.2)は、辺に重みを持たせた重み付きグラフでの最短路探索(本章では詳細を割愛)にどう一般化されるか。 - 第20章は「強連結なグラフは一意な定常分布を持つ」ことを最大希釈率による議論で示すが、この証明で使われるグラフの連結性の議論と、第9章で扱われる有向グラフの連結性(強連結性の定義自体は第9章では明示的に扱われていない)との関係は本 vault ではまだ整理されていない。 ## 関連 - 概念: [[二項関係]] / [[半順序]] / [[トポロジカルソート]] / [[同値関係]] / [[単純グラフ]] / [[ランダムウォーク]] / [[定常分布]] / [[PageRank]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] - 参考(別分野の概念、混同しないこと): [[グラフデータモデル]](データベースのグラフモデルであり本概念とは別物) ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 9, Chapter 20 §20.2.2-§20.2.3.