読者です 読者をやめる 読者になる 読者になる

「『数独』を数学する」を読みながらのメモ

 

 

この本を読んでいます.理由は,数独を解くスピードが遅いので,何らかの規則性を知りたいと思ったからです.
記事の目的は,記事の題名通りの予定です(2016/09/13現在).

 

p.25の以下の2文が引っ掛かりました.

 さらに驚いたことに、偶数の次数をもつ頂点が二つあるかゼロであるかは、必要条件であるだけではなく、十分条件である。言い換えれば、グラフに、奇数の次数をもつ頂点が二つかゼロの場合には、オイラー路あるいはオイラー閉路が存在するはずだということになる。

2文目は分かります.が,「言い換えれば」そうなるのか直感的に分かりませんでした.
つまり,「偶数の次数をもつ頂点がひとつまたは三つ以上ある場合は必要十分条件ではない(*)」
というわけで,(*)を考えます.

p.24で,

  • オイラー路は

    奇数の次数をもつ頂点が二つだけある (**)

  • オイラー閉路は

    奇数の次数をもつ頂点がひとつもない (***)

と説明してあるので,これを基にします.

(**)の否定は「偶数の次数をもつ頂点が二つでない(ひとつ以下または三つ以上) (**)’」
(***)の否定は「偶数の次数をもつ頂点がひとつ以上ある (***)’」
(**)’(***)’の積集合は「偶数の次数をもつ頂点がひとつまたは三つ以上ある」であり,この場合はオイラー路もオイラー閉路も存在しません.
これで(*)が言えました.