一筆書きの数学

前回、話の流れで五芒星の一筆書きに感動したということを書きました。
そこで一筆書きの話をしておきます。一筆書きの話でよく知られているのは「ケーニヒスベルクの７つの橋問題」だと思います。問題を考えやすくするために、４つの小島に７つの橋が架けられていることにします。

「同じ橋を２度以上渡らずに歩いて７つの橋を渡れるか」

というのが７つの橋問題です。もっと一般的な話は「ケーニヒスベルク　７つの橋」と検索すれば簡単にみつけられます。

なぜこれが一筆書きに関連するのかというと、橋を渡るということは島から島へと移ることですね。だから４つの島を点で表し橋を線で表すと次のような図形(７つ橋図)になります。これが一筆で書ければ７つの橋をそのように渡れば問題が解決します。

そこで、一筆で書けるとはどういうことかを考えてみます。

一筆で書けるということは、同じ道を通らずに出発点(始点)から到着点(終点)に行けるということなので、始点と終点が一致するか別の点かのいずれかです。だから始点終点が２つより多くなることはありません。

次に、ある一つの点で「出る」「入る」を考えると出入りの数が同じか異なるかのいずれかです。同じ場合は合計が偶数です。そこでこのような点を偶点と呼びます。異なる場合は一方が多くなるので必ず合計は奇数です。この点を奇点と呼びます。

一筆書きが出来るとき始点と終点が一致するか異なる点で終わるかのいずれかで、同じ点で終わるときはすべての点が偶点でなければなりません。なぜなら、始点終点が一致しているので出たら必ず入って終わり、その他の点は入って必ず出るからです。異なる点で終わる場合は奇点が２つだけで残りは偶点でなければなりません。

これを踏まえて７つ橋図を考えると奇点が４つなので一筆書きは不可能です。だからケーニヒスベルクの７つの橋問題も渡れないが答えです。

この説明は「一筆書きが出来るなら、奇点は０個または２個である」を示しただけなので、一筆書きが出来るための必要条件を与えただけです。でも対偶を考えることで「奇点が１個または３個以上なら一筆書きが出来ない」もいえます。
注意してほしいのは、奇点が０個または２個のときに一筆書きが出来るとは主張していないことです。結論は真(正しい)なのですがその証明は次回以降です。

次の図形が一筆書きできるか否かを判断し、可能な場合は実際に描いてみてください。▢