数学特別演習（第11回）

今日は「中国の郵便配達員問題」アルゴリズムの最後、入力が有向グラフの場合の話から始める、ということだったのですが、最初の担当の学生さんが、次の章からしか予習をしていません、ということで、急きょ、その場で発表をしてもらいました。

学生さんも、突然のことで面食らったと思いますが、私や、前回発表した人の説明を手がかりに、何とか無事この部分を終えることができました。

次の章では「ナイト跳び」の問題に関する議論が始まりました。これは、チェスの「ナイト」の駒を、チェス盤の上で動かし、すべてのマス目を一度だけ通過させることができるか？という問題です。ここでは「バックトラッキング法」や「ウォーンスドルフの方法」（1823年、ヒューリステックな方法）が紹介され、ついでオイラーによる研究成果（1757年）が紹介されました。ここでもオイラーが登場している。すごいです。

以上、最初の部分で詰まったことと、「ナイト跳び」の部分はよく準備してきたようなことから、最初の人に時間を使ってもらい、今日は1人で授業を終えました。

後で聞いたのですが、今日話した学生さんは、前回の2人目の人から、次の範囲が「ナイト跳び」から、と聞いていたのだそうで（私は前回の授業終了の際に、正しい範囲を伝えていたはずですが）、今日は本人もさぞかし驚いたことでしょう。でも、最後まできちんと説明していたのはよく頑張ったと思います。

そんなわけで、今日は予想外の展開になりましたが、今年の授業も今日で終わりです。よいクリスマス、お正月を過ごし、また年明けに元気に再会できることを願っています。