この章は、基本的なグラフ理論を思い出させることを意図している。読者があらかじめグラフアルゴリズムの知識があるのなら、始めるにあたりこの章は十分であろう。もし読者がグラフアルゴリズムの知識がないのならば、 Cormen, Leiserson, RivestのIntroduction to Algorithms のようなもっと詳しいものを薦める。
グラフ抽象
グラフは、多くの種類の問題を解くのに有効な数学的抽象化である。基本的には、グラフは頂点と辺から構成され、辺は二つの頂点を結ぶ。もっと正確には、グラフ(graph)とは組(V,E)で表され、Vは有限集合で、EはVの２項関係である。Vは 頂点集合(vertex set) と呼ばれ、その要素を 頂点(vertex) と呼ぶ。Eは辺の集合で、 辺(edge) とは(u,v)の組でu、vはVの要素である。 有向グラフ(directed graph) においては、辺は順序付けられた組で、 始点(source) を 終点(target) へと接続する。無向グラフ(undirected graph)においては、辺は順序付けされていない組で、２つの頂点を両方向につなぐ。つまり、無向グラフでは (u,v)と(v,u)は同じ辺の２通りの書き方である。
グラフのこの定義は、いくつかの点であいまいである。辺や頂点が何を表現するかが述べられていない。グラフの例としては、連絡道路やハイパーリンク付きのウェブページなどを挙げることができる。これらの詳細がグラフの定義からは除外されているのは、大きな理由がある。それらの詳細はグラフの 抽象化 の中では必要な部分ではない。詳細を定義から除外することで再利用可能な理論を構築でき、そのことは多くの異なった種類の問題を解く際に役に立つのである。
定義にもどろう。グラフは頂点と辺の集合である。実際の様子を見せるため、頂点に文字のラベルがついたグラフを考え、辺を単純に文字の組としよう。ここで、有向グラフの例を次のように書くことができる。
V = {v, b, x, z, a, y }
E = { (b,y), (b,y), (y,v), (z,a), (x,x), (b,x), (x,v), (a,z) }
G = (V, E)
このグラフを図示すると 図1 のようになる。辺 (x,x) は 輪(self-loop) と呼ばれる。(b,y)と (b,y)は 平行辺(parallel edges) であり、これは マルチグラフ(multigraph) でのみ許される(ただし、通常は有向グラフでも無向グラフでも許されない)。
図1: 有向グラフの例
次に似たようなグラフを示すが、今度は無向グラフである。これは図2に図示する。無向グラフでは輪は許されない。上記のグラフ(から平行辺(b,y)を除いたもの)の 無向版(undirected version) である。それはつまり、同じ頂点をもち、同じ辺から方向を除いたものを持つことを意味し、(a,z)と(z,a)という２つの辺は一つの辺に退化する。また、逆を考えることもできる。無向グラフの 有向版(directed version) は、すべての辺をそれぞれの方向を向く２つの辺で置き換えることで得られる。
V = {v, b, x, z, a, y }
E = { (b,y), (y,v), (z,a), (b,x), (x,v) }
G = (V, E)
図2: 無向グラフの例
ここでさらにグラフの用語を定義する。辺(u,v)がグラフに含まれるとき、頂点vは頂点uについて 隣接している(adjacent) と言う。有向グラフでは、辺(u,v)は 頂点uの 出辺(out-edge) であり、頂点vの 入辺(in-edge) である。無向グラフでは、辺(u,v)は頂点uとvを 接合している(incident on) という。
図1で、頂点yは頂点bに対して隣接している (ただしbはyに対して隣接していない)。辺(b,y)はbの出辺であり、yの入辺である。図2で、yはbに隣接していて、また逆も同様である。辺(y,b)は頂点yとbを接合している。
有向グラフにおいて、ある頂点の出辺の数は 出次数(out-degree) と呼ばれ、入辺の数は 入次数(in-degree) と呼ばれる。無向グラフにおいて、ある頂点に対して接合している辺の数は 次数(degree) と呼ばれる。図1で、頂点bの出次数は3であり、入次数は0である。図2では単純に頂点bの次数は2である。
グラフの 路(path) とは辺の列で、それぞれの辺の終点が次の辺の始点であるものである。頂点uから始まり頂点vで終わる路があれば、頂点vはuから 到達可能(reachable) であるという。路が 単純(simple) であるとは、辺の列の中でどの頂点も繰り返し現れないことである。路<(b,x), (x,v)>は単純であるが、路<(a,z), (z,a)>は単純ではない。また、路<(a,z), (z,a)>は最初の頂点と最後の頂点が一致するので、 サイクル(cycle) と呼ばれる。サイクルのないグラフは アサイクリック(acyclic) と呼ばれる。
平面的グラフ(planar graph) とは、すべての辺が交差しないように平面上に描けるグラフのことである。そのように描かれたものは 平面グラフ(plane graph) と呼ばれる。平面グラフの 面(face) とは、辺に囲まれた連結成分のことである。平面的グラフの重要な特性は、面、辺、頂点の数がオイラーの定理：|F| - |E| + |V| = 2によって関係付けられることである。このことは、平面的グラフは最大でもO(|V|)個の辺しか持たないことを意味する。
グラフデータ構造
データ構造を考えるときに最初に考えるべきグラフの属性は、まばらさ(sparsity) である。まばらさとは、頂点に対する相対的な辺の数である。EがV²に近いグラフは 密(dense) であると呼ばれ、E = alpha VでalphaがVより十分に小さい場合は、まばらな(sparse)グラフと呼ばれる。密なグラフについては、通常、 隣接行列表現(adjacency-matrix representation) が最良の選択であり、一方まばらなグラフについては 隣接リスト表現(adjacency-list representation) が最良である。また、まばらなグラフについては 辺リスト表現(edge-list representation) も適切な状況下では記憶効率面でよい選択である。
隣接行列表現
グラフの隣接行列表現はV x Vの２次元配列である。 行列auvの要素は、辺(u,v)がグラフに含まれるかどうかを示すブーリアン値である。図3に図1(から(b,y)を引いたもの)の隣接行列表現を表す。保存に必要な領域はO(V²)である。任意の辺について、アクセス、追加、除去にかかる時間はO(1)である。 頂点の追加や除去は、再割り当てとすべてのグラフのコピーが必要になり、手順数はO(V²)になる。adjacency_matrixクラスは、隣接行列表現によってBGLグラフインターフェースを実装する。
図3: 隣接行列によるグラフの表現
隣接リスト表現
グラフの隣接リスト表現では、すべての頂点に対して出辺の列を保存する。まばらなグラフでは、こうすることでメモリ領域を節約でき、必要な領域はO(V + E)だけになる。さらに、すべての頂点の出辺にはより効果的にアクセスできる。辺の挿入のコストはO(1)で、任意の辺へのアクセスはO(alpha)である。ここで、alphaは行列のまばらさ(グラフ中のすべての頂点についての出辺の数の最大値)である。図4は図1のグラフの隣接リスト表現である。adjacency_listは隣接リスト表現の実装である。
図4: 隣接リストによるグラフ表現
辺リスト表現
グラフの辺リスト表現は、単純に辺の列であり、辺は頂点のIDの組で表される。必要なメモリはO(E)だけである。辺挿入のコストはO(1)であり、特定の辺のアクセスするのはO(E)(あまり効果的でない)である。図5は図1のグラフの辺リスト表現である。edge_listアダプタクラスは、辺リスト表現の実装を作るのに使うことができる。
図5: 辺リストによるグラフの表現
グラフアルゴリズム
グラフ探索アルゴリズム
木辺(tree edge) とは、グラフ探索アルゴリズムをグラフに適用することによって作られた探索木(またはフォレスト)の辺ことである。辺(u,v)は木辺であるのは、辺(u,v)の探索(ビジタのexplore()メソッドにあたる)をしているときにvが最初に見つかるときである。後退辺(back edge)とは、探索木上で頂点を先祖につなぐ辺である。したがって、辺(u,v)ではvはuの先祖である。輪は後退辺とみなされる。先行辺(forward edge)は木辺ではない辺(u,v)で、探索木上uを子孫vへとつなぐ。交差辺(cross edge)とは、以上の３つのカテゴリに含まれない辺のことである。
幅優先探索
幅優先探索(Breadth-First Search, BFS)とは、グラフに対して横断的であり、特定の原点から到達可能な頂点をすべて探索する。また横断する順番については、頂点のすべての近傍を探索してから近傍の近傍の探索へと進む。幅優先探索について考えるには、例えば水溜りに石を落としたときに波が放射状に広がるように拡散すると思えばよい。同じ「波」の中の頂点は原点から同じ距離にある。頂点は最初にアルゴリズムによって遭遇するときに発見される(discovered)と言う。頂点は、その近傍がすべて探索されたときに完了した(finished)と言われる。これらをわかりやすくする例がある。グラフを図6に示し、そのBFSにおける発見と完了の順番をその下に示す。
図6: 広さ優先探索がグラフに広がる様子
- 発見の順番: s r w v t x u y
- 完了の順番: s r w v t x u y
sから開始して、最初はrとw(sの近傍)にたどり着く。sの両方の希望に到達してから、rの近傍(頂点v)に到達し、wの近傍tとxに到達する (rとwの順序は意味を持たない)。最後にtとxの近傍、uとyに到達する。
今グラフ上のどこにいるか、次にどこの頂点に行くかをアルゴリズムが把握するために、BFSは頂点に色を塗る。塗る色を置く場所は、グラフの中でもよいし、アルゴリズムに引数として渡すこともできる。
深さ優先探索
深さ優先探査(Depth-First Search, DFS) は、グラフ中の全頂点を探査する。このアルゴリズムでは、常にグラフ中の「深い」部分を、次に探査すべき辺として選択していく。これは、到達した頂点が未訪問の隣接頂点を持たなくなるまで次の未訪問な隣接頂点を選択していき、端に到達すれば前の頂点へと戻り、その頂点から任意の未探査な辺へと探査を継続していくことである。深さ優先探査は、出発する頂点から到達可能な全ての頂点を訪問した後に、残りの未訪問な頂点のうちから１頂点を選択して探査を継続していく。このプロセスは、深度優先の森からともに深度優先の木という集合を形成する。深さ優先探索は、グラフ中の辺を３つのカテゴリーに分類する：木辺、後退辺、先行辺か交差辺(どちらにも明確に分類しない)。与えられたグラフから多くの有効な深度優先の森が典型的に存在し、それゆえ辺を分類するには様々な(かつ等しく有効な)方法がある。
深さ優先探査の興味深い特性は、各頂点の発見時と完了時の間において、括弧（入れ子）構造を形成するということである。頂点が発見される場合、私たちが開いた括弧を使用すれば、頂点が探査終了される場合には閉じた括弧が使用され、その結果、括弧により適切に入れ子にされた集合ができあがる。図7は、探査された順番にラベル付けされた辺による無向グラフに適応された DFS （深さ優先探査）である。図の下に、探査を開始した順序と探査を終了した順序を示し、それらから導かれる括弧構造を示す。DFS （深さ優先探査）は、２つが接続されたコンポーネント・アルゴリズム、トポロジカル・ソート、などを含む他のグラフ・アルゴリズムによって使用される核となるアルゴリズムである。これは循環を検知するために利用できる（ファイル依存関係の例における循環依存 （Cylic Dependencies） の節を見よ）。
図 7: 無向グラフにおける深度優先探査
- 発見の順序: a b e d c f g h i
- 完了の順序: d f c e b a
- 括弧構造: (a (b (e (d d) (c (f f) c) e) b) a) (g (h (i i) h) g)
最小全域木問題
最小全域木問題は、以下のように定義される：グラフ E 中の全頂点を接続する循環のサブセット T を接続の全コストが最小となるように選択することである。全コストは下記により与えられる。
w(T) = T における辺 (u,v) におけるコスト w(u,v) の合計、 w(u,v) は辺 (u,v) のコスト
T は全域木(spanning tree)と呼ばれる.
最短経路問題
グラフ理論における古典的問題のひとつは、グラフ中の２頂点間を結ぶ最短経路を見つけることである。形式的に経路はグラフ G = (V, E) 中の頂点のシーケンス <v0,v1,...,vk> で表される（辺 (vi,vi+1) for i=0,1,...,k-1 は 辺の集合 E ）。シーケンスにおいて各頂点は次の頂点へ接続される。最短経路問題において、各辺は重みを数値として与えられている。それゆえ、経路の重み(weight of a path)について記す
w(p) = i=1..k of w(vi-1,vi) の合計
頂点 u から v に至る最短経路の重み(shortest path weight)は
delta (u,v) = min { w(p) : u --> v } もし 頂点 u から v に至る経路が存在すれば
delta (u,v) = 無限(infinity ) そうでなければ（ u から v に至る経路がなければ）
最短経路は、重みの合計が最小となる経路といえる。
最短経路問題には、いくつかの変形された問題がある。ここでは単一ペアの問題を定義した、しかし、さらに単一出所問題(グラフ中の1つの頂点から各頂点ごとまでの最短のパス)があり、等価な単一目的地問題、全ペア問題、などである。単一出所の問題を解決するアルゴリズムより漸近的に速い、単一ペアの問題を解決するアルゴリズムは存在しない。
最短経路木(shortest-paths tree)は、グラフ G=(V,E) 中のある頂点を原点とした有向サブグラフである。V' を V のサブセット、E' を E のサブセットとし、 V' はG' から到達可能な頂点の集合、G' は原点から連なる経路木を成すものとすれば、V' 中の全ての頂点 v は G' 中の頂点 v から唯一の経路を持つ。再帰的に、単一頂点アルゴリズムによる結果は最短経路木である。
ネットワークフロー問題
ネットワークの流れは送信(source)頂点 s から受信(sink)頂点tへと向かう有向グラフ G=(V,E) である。各辺は数値による、容量(capacity)関数 c 、および、流れ(flow)関数 f を持つ。流れ関数は次の３条件を満たしていなければならない：
f(u,v) <= c(u,v) for all (u,v) in V x V (容量制限)
f(u,v) = - f(v,u) for all (u,v) in V x V (流れ対称性)
sumv in V f(u,v) = 0 for all u in V - {s,t} (流れ保存則)
ネットワークにおける流れ(flow)は、受信頂点 t に流れ込む集合の流れである（それは、送信頂点 s から流れ出るネットの流れに等価である）。
|f| = sumu in V f(u,t) = sumv in V f(s,v)
辺における余剰容量(residual capacity)を r(u,v) = c(u,v) – f(u,v) とする。 r(u,v) > 0 を満たす辺は余剰辺 Ef であり、それは余剰グラフ Gf = (V, Ef) を成す。 r(u,v) = 0 を満たす辺は飽和(saturated)している。
最大流問題(maximum flow problem)は、最大に可能な流量値 |f| を決定することであり、そのときのグラフ中における各辺に対する流量値を決定することである。
ネットワークの流れを 図 8 に示す。 A は送信頂点で、H は受信頂点。
図 8: 最大流ネットワーク。各辺は（流れ/容量）のラベルで示している。
最大流ネットワーク問題を解決するには長い歴史があり、最初のアルゴリズムは Ford と Fulkersonによる。現在に至る最良のアルゴリズムである push-relabel アルゴリズムは Goldberg によるもので、これは Karzanov による preflow introduced という概念を元に成り立っている。
Copyright © 2000-2001 Jeremy Siek, Indiana University (jsiek@osl.iu.edu)
Japanese Translation Copyright © 2003 KATO Kimikazu, OKI Miyuki
Japanese Translation Copyright © 2014 Akira Takahashi
オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、その利用が適していることを関知しない。