PRML演習問題 8.2(基本) www

問題

有向グラフにおいて、すべてのノードについて自分より小さい番号を持つノードに向かうリンクが存在しないように
ノードを順序付けることができるなら、有向閉路は存在しないことを示せ。

解答

問題の対偶を考えます。

有向閉路は存在するなら、
有向グラフにおいて、すべてのノードについて自分より小さい番号を持つノードに向かうリンクが存在しないように
ノードを順序付けることができない。

は必ず成り立つので、題意が示せました。

補足

の場合で考えると分かりやすいかもしれません。