- 831 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 17:21:09 ]
- >>830
それを定義に採用するなら，DAGでなくてもいいよ．
ただ，普通はそれを定義にはしない．
（それは，トポロジカルソートのひとつを求めるアルゴリズム）
普通のトポロジカルソートの定義は頂点への番号付け（並び順）σで，
u から v に枝があるとき σ(u) < σ(v) なるものを言うんだけど，
これだと u → v → w → u なるサイクルがあると
σ(u) < σ(v) < σ(w) < σ(u) で番号付けに矛盾する．
