【グラフ理論】ケーニヒスベルクの橋を解説！【パリティのチェック】

こんにちは。タクマ™ [@suwaru_blog] です。

前回、パリティについて解説しました。

ケーニヒスベルグの橋

哲学者カントの故郷ケーニヒスベルグには、
川で区切られた 4 つの土地・土地を結ぶ 7 つの橋がありました。

以下の条件で 7 つの橋すべてを渡りつくすことはできるでしょうか？

また、渡りつくすことはできない場合、それをどうやって証明すればよいでしょうか？

グラフ理論

数学者オイラーはこの問題を解き明かし、それはグラフ理論と呼ばれています。
グラフ理論に従い、土地の繋がり方を図式化 (グラフ化) してみましょう。

土地 A, B, C, D のことを「頂点」と呼び、
頂点どうしを結ぶ橋 a, b, c, d, e, f, g のことは「辺」と呼ぶことにします。

次数

頂点からは複数の辺が伸びています。
頂点から伸びている辺の数を「次数」と呼ぶことにします。

また次数が偶数の頂点は「偶点」、次数が奇数の頂点は「奇点」と呼ぶことにします。

減らし歩き

頂点は次数を消費します。

通った辺にチェックをつけて、その頂点の次数を減らすという考え方です。
次数が減るということは「偶点・奇点が変化する可能性がある」ので、それもチェックします。

このテクニックを「減らし歩き」と呼ぶことにします。

一筆書きできるということは「すべての頂点の次数が 0 になる」ということ

一筆書きできるということは、減らし歩きの結果「すべての頂点の次数が 0 になる」を意味します。
奇点があったら、その頂点には通っていない辺が残っています。

なぜなら経由するとき、偶奇は変化しないからです。

スタート・ゴールの頂点が一致する場合

スタート・ゴールの頂点が一致する場合…

なぜならスタートするとき・ゴールするときで、その頂点の次数が 1 ずつ減るので、
次数が合計 2 減ることになり、最終的な偶奇は変化しないためです。

つまり、スタート・ゴールの頂点が一致する場合は「すべての頂点が遇点である」必要があります。

スタート・ゴールの頂点が一致しない場合

スタート・ゴールの頂点が一致しない場合…

なぜならスタートするとき・ゴールするときで、それぞれの頂点の次数が 1 ずつ減るので、
最終的な偶奇が変化するためです。

つまり、スタート・ゴールの頂点が一致しない場合は「奇点が 2 個である」必要があります。

答え

一筆書きの条件は「すべての頂点が偶点」または「奇点が 2 個」であることがわかりました。
含意の論理をつかうと 一筆書きができる ⇒ (ならば) 「すべての頂点が偶点」または「奇点が 2 個」 です。

奇点が 4 つであることを理由に「橋を渡りつくすことはできない」を証明することができます。
重要なことは、全パターン試行錯誤しなくても「不可能であることを証明できる」です。

オイラーは辺の数そのものではなく、辺の「偶奇」に注目しました。
これも前回の記事で紹介したパリティのチェックの一種です。

CS シリーズ

次回

前回