9-1 幅優先探索と深さ優先探索
前提知識：距離・直径・中心
同じ頂点を何度も調べない
graphを手で眺めるだけなら、「隣へ進み、まだ見ていない頂点を調べる」で十分です。算法にするには、
- どの頂点を既に発見したか
- 次にどの頂点を処理するか
- どの辺から初めて到達したか
を明示的に記録する必要があります。
breadth-first search（BFS）は始点から近い順に探索し、最短距離を求めます。depth-first search（DFS）は一方向へ進めるだけ進み、戻りながら探索します。その再帰的な入れ子構造からcycle、bridge、cut vertexを検出できます。
隣接listと計算量
各頂点 $v$ に対し、その近傍を並べたlist
$$
\operatorname{Adj}[v]
$$
を用意します。無向graphでは各辺 $uv$ が $\operatorname{Adj}[u]$ と $\operatorname{Adj}[v]$ に一度ずつ現れるため、list全体の長さは
$$
\sum_{v\in V}\deg(v)=2|E|
$$
です。
本章では、配列の読み書き、queue・stackへの追加と削除、隣接listの一要素を見る操作をそれぞれ定数時間と数えます。このmodelで $O(|V|+|E|)$ は、入力の隣接listを定数回読む程度の時間です。
キュー|queueは、先に入れた要素を先に取り出す先入れ先出し|first-in first-out構造である。
スタック|stackは、後に入れた要素を先に取り出す後入れ先出し|last-in first-out構造である。
BFSはqueueを使います。再帰的DFSでは、未完了の呼び出し列が暗黙のstackになります。
breadth-first search
連結graph $G$ と始点 $s$ に対するBFSを次のように定めます。未発見を $\infty$ で表します。
for each v in V(G):
dist[v] = infinity
parent[v] = null
dist[s] = 0
Q = empty queue
enqueue(Q, s)
while Q is not empty:
u = dequeue(Q)
for each v in Adj[u]:
if dist[v] = infinity:
dist[v] = dist[u] + 1
parent[v] = u
enqueue(Q, v)
頂点は未発見から発見済みへ一度だけ変わります。発見時にqueueへ一度だけ入り、一度だけ取り出されます。
連結graph $G$ で、始点 $s$ 以外の各頂点 $v$ とparent $p(v)$ を結ぶ辺全体は、$G$ の全域木をなす。
連結性により、BFSは最終的に全頂点を発見します。実際、未発見頂点があるなら、$s$ からその頂点へのpath上で最初の未発見頂点を $v$、その直前を $u$ と取れます。$u$ は発見済みでいつかqueueから取り出されるため、辺 $uv$ を調べた時点で $v$ も発見され、矛盾します。
各 $v\ne s$ は初めて発見されたとき一つのparentをもちます。parent辺を逆向きにたどるたび
$$
\operatorname{dist}[p(v)]
=\operatorname{dist}[v]-1
$$
なので、有限回でdistが0の $s$ へ到達します。従ってparent辺だけで各頂点は $s$ と結ばれます。
またparentをたどるとdistが真に減るため、parent辺にcycleはありません。全頂点を含み連結でcycleをもたないので全域木です。□
BFSは最短距離を求める
BFS終了後、すべての $v\in V(G)$ に対して
$$
\operatorname{dist}[v]=d_G(s,v).
$$
さらにBFS parent treeでの $s$–$v$ pathは $G$ のgeodesicである。
parentを $v$ から $s$ までたどると、distが一つずつ減るので、長さ $\operatorname{dist}[v]$ の $s$–$v$ pathが得られます。従って
$$
d_G(s,v)\le\operatorname{dist}[v].
$$
逆向きを示します。$s=v_0,v_1,\ldots,v_k=v$ を最短pathとし、$k=d_G(s,v)$ とします。$i$ に関する帰納法で
$$
\operatorname{dist}[v_i]\le i
$$
を示します。
$i=0$ では $\operatorname{dist}[s]=0$ です。$v_{i-1}$ が発見されればいつかqueueから取り出され、隣接頂点 $v_i$ を調べます。その時点で $v_i$ が未発見なら
$$
\operatorname{dist}[v_i]
=\operatorname{dist}[v_{i-1}]+1
\le i.
$$
既に発見済みなら、そのdistは初回発見時に設定されており、BFSのqueueが非減少dist順に頂点を取り出すことからやはり $i$ 以下です。
最後の点を明示します。distが $r$ の頂点が取り出されると、その未発見近傍には $r+1$ が付いてqueue末尾へ入ります。その時queueに既にある頂点のdistは $r$ または $r+1$ であり、以後も先頭から取り出すので、取り出されるdistは非減少です。従って $v_i$ が既に発見済みなら、$v_{i-1}$ を処理する時点でそのdistは $\operatorname{dist}[v_{i-1}]+1\le i$ 以下です。
よって
$$
\operatorname{dist}[v]\le k=d_G(s,v).
$$
二つの不等式から等号を得ます。parent pathの長さもこの値なのでgeodesicです。□
非連結graph
一つの始点からのBFSはその連結成分だけを訪れます。未発見頂点を新しい始点としてBFSを繰り返せば、各成分に一本ずつBFS treeをもつBFS forestが得られ、連結成分も列挙できます。
depth-first search
DFSは頂点を発見すると、未発見の隣接頂点へただちに再帰します。
time = 0
for each v in V(G):
state[v] = unvisited
parent[v] = null
for each root r in V(G):
if state[r] = unvisited:
DFS-Visit(r)
DFS-Visit(u):
state[u] = active
time = time + 1
disc[u] = time
for each v in Adj[u]:
if state[v] = unvisited:
parent[v] = u
DFS-Visit(v)
state[u] = finished
time = time + 1
finish[u] = time
未発見頂点へ進んだ辺をDFS tree辺と呼びます。外側のloopで複数のrootが選ばれる場合、tree辺全体はDFS forestをなします。
DFSのparent辺全体は、各連結成分を覆うrooted treeのdisjoint unionをなす。
各root以外の発見済み頂点は、未発見からactiveへ変わる瞬間にただ一つのparentを得ます。parentの発見時刻は子より早いので、parent辺を逆向きにたどってcycleへ戻ることはありません。従ってparent辺全体はforestです。
一つのroot $r$ から始まった再帰が終了したとき、$r$ の連結成分内に未発見頂点は残りません。残るとすれば、$r$ からその頂点へのpath上で発見済み頂点から未発見頂点へ初めて移る辺があり、前者を処理したとき後者を再帰訪問するはずだからです。従って各DFS treeは一つの連結成分を覆います。□
発見時刻と終了時刻
各頂点 $u$ に区間
$$
I(u)=[\operatorname{disc}(u),\operatorname{finish}(u)]
$$
を対応させます。
異なる二頂点 $u,v$ に対し、区間 $I(u),I(v)$ は互いに素であるか、一方が他方へ真に含まれる。
さらに $v$ がDFS forestで $u$ の子孫であることと
$$
\operatorname{disc}(u)
<\operatorname{disc}(v)
<\operatorname{finish}(v)
<\operatorname{finish}(u)
$$
は同値である。
$u$ がactiveである間に $v$ が未発見隣接頂点からの再帰を通じて発見されると、$v$ の再帰呼び出し全体は $u$ の呼び出しが終了する前に完了します。従って
$$
\operatorname{disc}(u)
<\operatorname{disc}(v)
<\operatorname{finish}(v)
<\operatorname{finish}(u),
$$
であり、$v$ は $u$ の子孫です。
$u$ の呼び出し終了後に $v$ が発見されるなら
$$
\operatorname{finish}(u)<\operatorname{disc}(v)
$$
で二区間は互いに素です。$v$ が先に発見される場合は $u,v$ を交換した同じ二場合です。
再帰呼び出しがstackから戻る順序により、区間が真に含まれる場合の内側の頂点は外側の頂点の再帰中に発見され、そのDFS subtreeに属します。従って子孫条件との同値も得られます。□
この性質は括弧列と同じです。発見を開き括弧、終了を閉じ括弧とすれば、DFSは正しく入れ子になった括弧列を作ります。
無向DFSの非tree辺
無向graphのDFSで、tree辺でない任意の辺 $uv$ は、$u,v$ の一方が他方のDFS ancestorである。
$u$ の方が先に発見されたとします。$u$ の隣接listで辺 $uv$ を調べる時点を考えます。
$v$ が未発見なら $uv$ はtree辺になるので、仮定に反します。従って $v$ は既に発見済みです。
$v$ がactiveなら、$u,v$ はともに現在の再帰stack上にあります。stack上のactive頂点はancestor順に並び、$u$ の方が先に発見されているので $u$ は $v$ のancestorです。
$v$ が既にfinishedなら、$u$ の呼び出しがactiveな間に $v$ の呼び出しが開始・終了したことになります。parenthesis theoremから
$$
I(v)\subset I(u)
$$
であり、$v$ は $u$ の子孫です。
いずれの場合も二端点はancestor–descendant関係にあります。□
tree辺でない辺を、深い側から浅いancestorへ向けてback edgeと呼びます。無向DFSには別subtreeどうしを結ぶcross edgeがありません。
low値
DFS treeの頂点 $v$ に対し、そのsubtreeからtree辺を下へ任意回進み、最後に高々一本のback edgeを使って到達できる最も早いancestorを記録します。
$$
\operatorname{low}(v)
$$
を、次の時刻の最小値とし、この量をlow値という。
- $\operatorname{disc}(v)$。
- $v$ の深さ優先探索|DFS subtree内の頂点 $x$ からancestor $w$ への後退辺|back edge $xw$ があるときの $\operatorname{disc}(w)$。
頂点 $v$ のDFS childrenを $c$、$v$ からancestor $w$ へのback edgeを $vw$ とすると
$$
\operatorname{low}(v)
=\min\left(
\operatorname{disc}(v),
\min_{vw\text{ back edge}}\operatorname{disc}(w),
\min_{c\text{ child of }v}\operatorname{low}(c)
\right).
$$
空の最小値は無視する。
$v$ のsubtree内の頂点は $v$ 自身、またはただ一つのchild $c$ のsubtreeに属します。
back edgeの深い端が $v$ 自身なら第二項に現れます。深い端がchild $c$ のsubtree内なら、そのback edgeが到達する最小発見時刻は $\operatorname{low}(c)$ に含まれます。back edgeを使わず $v$ 自身にとどまる場合が第一項です。
すべての場合を排反に尽くして最小を取っているため、再帰式が従います。□
DFSの再帰から戻るとき、childrenのlow値は既に計算済みです。従ってこの式はbottom-upに計算できます。無向辺 $v\,p(v)$ をback edgeとして数えないことが重要です。同じ辺を親へ戻っただけでcycleがあると誤判定してしまうからです。
low値によるbridge判定
DFS tree辺 $uv$ で $u=p(v)$ とする。このとき
$$
uv\text{ がbridge}
\quad\Longleftrightarrow\quad
\operatorname{low}(v)>\operatorname{disc}(u).
$$
$\operatorname{low}(v)\le\operatorname{disc}(u)$ とします。定義により、$v$ のsubtree内のある頂点 $x$ から、$u$ またはそのancestor $w$ へのback edgeがあります。DFS tree内で $v$ から $x$ へ下り、back edgeで $w$ へ戻り、tree内で $w$ から $u$ へ下ると、辺 $uv$ を使わない $v$–$u$ pathが得られます。従って $uv$ はcycleに属し、bridgeではありません。
逆に $\operatorname{low}(v)>\operatorname{disc}(u)$ とします。$v$ のsubtreeから $u$ または $u$ より上のancestorへ戻るback edgeはありません。無向DFSの非tree辺はancestor–descendantを結ぶため、$v$ のsubtreeからその外へ出る辺はtree辺 $uv$ しかありません。$uv$ を削除すると $v$ のsubtreeが残りから切り離されるので、$uv$ はbridgeです。□
low値によるcut vertex判定
DFS rootとそれ以外では条件が異なります。
連結graphのDFS treeを考える。
- root $r$ は、DFS childrenを二つ以上もつとき、かつそのときに限りcut vertexである。
- rootでない頂点 $u$ は、あるDFS child $v$ が
$$ \operatorname{low}(v)\ge\operatorname{disc}(u) $$
を満たすとき、かつそのときに限りcut vertexである。
まずrootを考えます。rootの異なるchild subtreesの間に辺があれば、その辺は一方の頂点を他方のancestorへ結ぶ必要があります。しかし二つのsubtreeの頂点はancestor–descendant関係にないので、無向DFSのancestor性に反します。従って異なるchild subtreesの間に辺はありません。
childrenが二つ以上なら、rootを削除すると異なるsubtreeが分離するためcut vertexです。childが一つだけなら、そのsubtreeがroot以外の全頂点を含み連結なので、rootを削除しても連結です。
次にrootでない $u$ を考えます。child $v$ が
$$
\operatorname{low}(v)\ge\operatorname{disc}(u)
$$
を満たすと、$v$ のsubtreeから $u$ の真のancestorへ戻るback edgeがありません。subtree外への非tree辺はancestorへしか行けず、$u$ 自身より上へ出られないため、$u$ を削除すると $v$ のsubtreeは残りから切り離されます。従って $u$ はcut vertexです。
逆にすべてのchild $v$ が
$$
\operatorname{low}(v)<\operatorname{disc}(u)
$$
を満たすとします。各child subtreeから $u$ の真のancestorへ戻るback edgeがあります。$u$ を削除しても、各child subtreeはそのback edgeを通じて $u$ のancestor側へ接続します。$u$ のsubtree外の頂点もparentを通じてancestor側にあり、すべてが同じ成分に残ります。従って $u$ はcut vertexではありません。□
bridge条件が厳密不等号 $>$、cut vertex条件が $\ge$ である違いに注意してください。child subtreeから $u$ 自身へback edgeがある場合、tree辺 $uv$ はcycleに入るのでbridgeではありません。しかし $u$ を削除すると、そのback edgeも消えるためsubtreeが分離し得ます。
一つの具体例
頂点
$$
\{a,b,c,d,e,f\}
$$
と辺
$$
ab,\ ac,\ bc,\ cd,\ de,\ ef,\ fd
$$
をもつgraphを考えます。二つの三角形 $abc$ と $def$ がbridge $cd$ で結ばれています。
BFSを $a$ から行うと、距離は
$$
\begin{array}{c|cccccc}
v&a&b&c&d&e&f\\ \hline
d(a,v)&0&1&1&2&3&3
\end{array}
$$
です。
DFSが
$$
a\to b\to c\to d\to e\to f
$$
の順にtree辺を選び、back edge $ca,fd$ を見つけたとします。発見時刻だけを $1,2,\ldots,6$ と簡略化して書けば
$$
\begin{array}{c|cccccc}
v&a&b&c&d&e&f\\ \hline
\operatorname{disc}(v)&1&2&3&4&5&6\\
\operatorname{low}(v)&1&1&1&4&4&4
\end{array}
$$
です。
tree辺 $cd$ では
$$
\operatorname{low}(d)=4>\operatorname{disc}(c)=3
$$
なのでbridgeです。頂点 $c$ はchild $d$ に対し $4\ge3$、頂点 $d$ はchild $e$ に対し $4\ge4$ なのでcut vertexです。他の非root頂点は条件を満たさず、root $a$ のDFS childは一つなのでcut vertexではありません。
計算量
隣接listで表された有限graphに対し、BFSとDFSはいずれも
$$
O(|V|+|E|)
$$
時間、$O(|V|)$ の補助記憶で実行できる。DFSでdisc・finish・lowを計算し、bridgeとcut vertexを列挙しても同じ漸近計算量である。
各頂点は一度だけ未発見から発見済みになります。BFSではqueueへ一度入り一度出て、DFSでは一度だけ再帰呼び出しされます。従って頂点に関する処理は $O(|V|)$ です。
各頂点の隣接listは、その頂点を処理するとき一度走査されます。無向辺は両端のlistに一度ずつ現れるので、隣接list要素の総数は $2|E|$。従って辺に関する処理は $O(|E|)$ です。
dist、state、parent、disc、finish、lowなどは各頂点あたり定数個の値です。queueまたは再帰stackも高々 $|V|$ 頂点を保持するので補助記憶は $O(|V|)$ です。
lowの更新とbridge・cut判定は各tree辺・back edgeを調べる際の定数回の比較だけなので、時間の次数を増やしません。□
隣接行列を使うと、各頂点の全 $|V|$ 候補を調べるため、疎なgraphでも通常 $O(|V|^2)$ 時間になります。密なgraphでは $|E|$ 自体が $\Theta(|V|^2)$ なので、両表現の次数は一致します。
有向非巡回graphとtopological sort
順序制約を有向辺 $u\to v$ で表し、「$u$ を $v$ より先に処理する」と読みます。全ての制約を同時に満たす並べ方があるためには、有向cycleがあってはいけません。例えば
$$
v_1\to v_2\to\cdots\to v_k\to v_1
$$
があれば、$v_1$ は $v_2$ より前、従って $v_k$ より前でなければならない一方、最後の辺は $v_k$ を $v_1$ より前に要求します。
有限有向graph $D=(V,A)$ のトポロジカル順序|topological orderingとは、全頂点を一度ずつ並べた列
$$
v_1,v_2,\ldots,v_n
$$
であって、全てのarc $v_i\to v_j$ に対して $i< j$ を満たすものである。
入次数0の頂点を一つ出力し、その頂点と外向きarcを削除する操作を繰り返す算法をKahn算法と呼びます。次の補題が、途中で必ず次の頂点を選べることを保証します。
空でない有限有向graph $D$ が有向cycleをもたないなら、入次数0の頂点を少なくとも一つもつ。
反対に全頂点の入次数が1以上だと仮定します。任意の頂点 $v_0$ から始め、$v_0$ へ入るarcの始点を $v_1$、$v_1$ へ入るarcの始点を $v_2$ と選び続けます。すなわち各 $i$ で
$$
v_{i+1}\to v_i
$$
です。
頂点は有限個なので、列 $v_0,v_1,v_2,\ldots$ には同じ頂点が二度現れます。$v_p=v_q$、$p< q$ とすれば
$$
v_q\to v_{q-1}\to\cdots\to v_p=v_q
$$
は有向cycleです。仮定に反するので、入次数0の頂点が存在します。□
有限有向graph $D$ について、次は同値である。
- $D$ は有向cycleをもたない。
- $D$ はtopological orderingをもつ。
- Kahn算法は全頂点を出力して停止する。
隣接listと各頂点の入次数を用いれば、Kahn算法は $O(|V|+|A|)$ 時間で実行できる。
$2\Rightarrow1$ を示します。topological ordering中の有向cycle
$$
v_{i_1}\to v_{i_2}\to\cdots\to v_{i_k}\to v_{i_1}
$$
を仮定します。cycle上で添字が最大の頂点を $v_{i_r}$ とすれば、その次のarcはより大きな添字へ進まなければならず、最大性に反します。従って有向cycleはありません。
$1\Rightarrow3$ を示します。まだ頂点が残っている各段階で、残った誘導部分graphも有向cycleをもちません。前補題により入次数0の頂点があるので、Kahn算法は停止せず一頂点を出力できます。有限回後に全頂点を出力します。
$3\Rightarrow2$ を示します。arc $u\to v$ を考えます。$u$ を出力する前に $v$ が出力されたなら、その時点で $u\to v$ が残っているため $v$ の入次数は正であり、選択規則に反します。従って必ず $u$ が $v$ より先に出力され、出力列はtopological orderingです。
計算量も確認します。最初に全arcを一度調べて入次数を計算し、入次数0の頂点をqueueへ入れます。各頂点は一度だけqueueへ入り、各arc $u\to v$ は $u$ を削除するとき一度だけ調べられ、その際に $v$ の入次数を1減らします。従って総時間は $O(|V|+|A|)$、補助記憶は $O(|V|)$ です。□
これは「極小元を一つ選んで削除する」線形拡張算法と同じ構造です。有向非巡回graphから、$u\to v$ なら $u< v$ とする到達可能性順序を作れば、入次数0の頂点は極小元に対応します。探索算法と順序集合の算法が、同じ有限降下を別の言葉で見ているのです。
演習
頂点
$$
\{s,a,b,c,d,e\}
$$
と辺
$$
sa,\ sb,\ ac,\ bc,\ bd,\ ce,\ de
$$
をもつgraphで、$s$ からの距離をすべて求めよ。近傍をalphabet順に調べるBFS parent treeも一つ示せ。
$s$ の近傍 $a,b$ は距離1です。$a$ から $c$、$b$ から $d$ が初めて発見され、距離2です。$c$ または $d$ から $e$ が発見され、距離3です。従って
$$
\begin{array}{c|cccccc}
v&s&a&b&c&d&e\\ \hline
d(s,v)&0&1&1&2&2&3
\end{array}
$$
です。
alphabet順なら $a$ を $b$ より先に処理し、$c$ を $d$ より先に処理します。parentは
$$
p(a)=s,\quad p(b)=s,\quad
p(c)=a,\quad p(d)=b,\quad p(e)=c
$$
と取れます。parent辺は
$$
sa,sb,ac,bd,ce
$$
です。□
BFSのqueue内では、任意の時点でdist値が二種類以下であり、先頭から非減少順に並ぶことを証明せよ。
帰納法で示します。最初のqueueは $s$ 一つで成立します。
先頭の頂点 $u$ のdistを $r$ とします。帰納法の仮定により、queueの残りはdist $r$ の頂点、その後にdist $r+1$ の頂点という順です。$u$ の未発見近傍へ付く値は $r+1$ で、queue末尾へ追加されます。従って追加後も、残っている $r$ の頂点の後に $r+1$ の頂点が並びます。
最後のdist $r$ 頂点を取り出した後は、$r+1$ の頂点と、そこから新しく加わる $r+2$ の頂点だけになります。よって常に二種類以下で非減少順です。□
DFSで
$$
\operatorname{disc}(u)=2,\quad
\operatorname{finish}(u)=11,
$$
$$
\operatorname{disc}(v)=4,\quad
\operatorname{finish}(v)=7,
$$
$$
\operatorname{disc}(w)=12,\quad
\operatorname{finish}(w)=15
$$
であった。$u,v,w$ のancestor関係を判定せよ。
$$
[4,7]\subset(2,11)
$$
なので、parenthesis theoremから $v$ は $u$ の真の子孫です。
$w$ の区間 $[12,15]$ は $u$ の区間 $[2,11]$ と互いに素なので、$u,w$ はどちらも他方のancestorではありません。$v$ の区間とも互いに素なので、$v,w$ にもancestor関係はありません。□
DFS tree辺が
$$
ra,\ ab,\ bc,\ ad
$$
で、発見時刻とlow値が
$$
\begin{array}{c|ccccc}
v&r&a&b&c&d\\ \hline
\operatorname{disc}(v)&1&2&3&4&5\\
\operatorname{low}(v)&1&2&2&2&5
\end{array}
$$
であるとする。bridgeをすべて求めよ。
各parent–child辺で比較します。
$$
\operatorname{low}(a)=2
>\operatorname{disc}(r)=1
$$
なので $ra$ はbridgeです。
$$
\operatorname{low}(b)=2
\not>\operatorname{disc}(a)=2
$$
なので $ab$ もbridgeでありません。
$$
\operatorname{low}(c)=2
\not>\operatorname{disc}(b)=3
$$
なので $bc$ もbridgeでありません。
$$
\operatorname{low}(d)=5
>\operatorname{disc}(a)=2
$$
なのでbridgeは $ra$ と $ad$ の二本です。□
前問と同じDFS dataを用い、root $r$ のchildが $a$ 一つだけであるとする。cut vertexを判定せよ。
root $r$ のDFS childは一つだけなので、$r$ はcut vertexではありません。
$a$ にはchild $b,d$ があります。
$$
\operatorname{low}(b)=2\ge\operatorname{disc}(a)=2
$$
であり、また $\operatorname{low}(d)=5\ge2$ なので $a$ はcut vertexです。
$b$ のchild $c$ について
$$
\operatorname{low}(c)=2<\operatorname{disc}(b)=3
$$
なので $b$ はcut vertexではありません。$c,d$ はchildをもたないのでcut vertex条件を満たしません。従ってcut vertexは $a$ だけです。□
$n$ 頂点、$m$ 辺のgraphで、隣接listと隣接行列を用いるBFSの時間量を比較せよ。特に $m=n-1$ と $m=\binom n2$ の場合を述べよ。
隣接listでは各頂点と各辺を定数回処理するので
$$
O(n+m)
$$
です。隣接行列では各頂点を処理するたびに一行の $n$ 成分を調べるため
$$
O(n^2)
$$
です。
$m=n-1$ の木では隣接listは $O(n)$、隣接行列は $O(n^2)$ です。
完全graphでは
$$
m=\binom n2=\Theta(n^2)
$$
なので、隣接listも
$$
O(n+m)=O(n^2)
$$
となり、隣接行列と同じ次数です。□
頂点集合 $\{a,b,c,d,e\}$ とarc
$$
a\to c,\quad b\to c,\quad b\to d,\quad c\to e,\quad d\to e
$$
をもつ有向graphにKahn算法を適用し、topological orderingを一つ求めよ。さらにarc $e\to b$ を加えると算法が全頂点を出力できないことを示し、残る有向cycleを一つ挙げよ。
初めの入次数は
$$
\deg^-(a)=\deg^-(b)=0,\quad
\deg^-(c)=2,\quad
\deg^-(d)=1,\quad
\deg^-(e)=2
$$
です。まず $a$、次に $b$ を選ぶと、$a\to c,b\to c,b\to d$ が削除されて $c,d$ の入次数が0になります。続いて $c,d$ をこの順に選べば、最後に $e$ の入次数が0になります。従って
$$
a,b,c,d,e
$$
はtopological orderingです。$a,b,d,c,e$ も可能です。
$e\to b$ を加えると、最初に入次数0なのは $a$ だけです。$a$ を削除した後、$b,c,d,e$ の入次数は全て正なので算法は停止します。実際、残ったgraphには
$$
b\to c\to e\to b
$$
という有向cycleがあります。全頂点を出力できないことは、topological ordering theoremによりcycle存在の証明にもなります。□
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
