計算アルゴリズム【Ⅱ】

計算アルゴリズム【Ⅱ】 at TECH

831:デフォルトの名無しさん
08/12/02 17:21:09
>>830
それを定義に採用するなら，DAGでなくてもいいよ．
ただ，普通はそれを定義にはしない．
（それは，トポロジカルソートのひとつを求めるアルゴリズム）

普通のトポロジカルソートの定義は頂点への番号付け（並び順）σで，
u から v に枝があるとき σ(u) < σ(v) なるものを言うんだけど，
これだと u → v → w → u なるサイクルがあると
σ(u) < σ(v) < σ(w) < σ(u) で番号付けに矛盾する．

次ページ

続きを表示

1を表示