問題
有向グラフにおいて, すべてのノードについて自分より小さい番号を持つノードに向かうリンクが存在しないようにノードを順番付けることができるなら有向閉路は存在しないことを示せ.
#方針
問題で与えられている命題は
A: すべてのノードについて自分より小さい番号を持つノードに向かうリンクが存在しないようにノードを順番付けることができる
B: 有向閉路は存在しない
A$\Longrightarrow$Bである. 全てのノードについて考えるのは困難であるため対遇を取ることによって証明を簡単な条件に落とし込んでいく.すなわち
$\bar{A}$: あるノードについて自分より小さい番号を持つノードに向かうリンクが存在しないようにノードを順番付けることができる
$\bar{B}$: 有向閉路は存在する
$\bar{B}\Longrightarrow\bar{A}$を考える.
#解答
有向閉路とは, あるノードから出発して矢印に従って進んだ後, また始めのノードに戻ってくるような閉じた経路のことである.
つまり始めのノードに戻るということは必ず自分より大きい番号に向かうリンクが存在する.したがって$\bar{A}$を満たすような経路が存在することがわかったので, 命題$\bar{B}\Longrightarrow\bar{A}$は正である. したがって対偶が正であるので元の命題も正である. 題意は示された.