【一筆書きの数学】一筆書きができる必要十分条件とは？(証明あり)

こんにちは。福田泰裕です。

突然ですが、問題です。
次のうち、一筆書きができる図はどれでしょう？

おそらくこういった「一筆書きができるか」という問題は、子どもの頃に遊んだ経験があると思います。

今回は、一筆書きができる図形とはどんな性質をもっているのかを解説します。

最後まで読んでいただけると嬉しいです。

一筆書き問題のはじまり：ケーニヒスベルクの橋渡り問題

一筆書きの問題が考えられるようになったのは、18世紀頃だと言われています。

1736年のプロイセン、ケーニヒスベルク（現在はロシアのカリーニングラード）という街があります。
あの有名な哲学者のカントも住んでいたといわれる街です。
このケーニヒスベルクには大きな川が流れており、街には7つの橋が架けられていました。

同じ道を通らずに、この7つの橋をちょうど1回だけ渡ってもとに戻ってくる散歩コースは存在するだろうか…ということをカントが考えていたかどうかは分かりませんが、これがケーニヒスベルクの橋渡り問題です。

試しに線を引いて考えてみましょう。

何度やってもうまくいきません‥‥‥。

日常生活においては「何度やってもできないんだから、一筆書きのコースは存在しないのだろう」で十分なのですが、数学の世界ではそうはいきません。
本当に一筆書きのコースが存在しないのか、考えていきましょう。

グラフの定義

まずグラフというものを定義します。

いくつかの点を、いくつかの線で結んだ図形をグラフということにしましょう。

先ほどのケーニヒスベルクの街を簡略化して、グラフにしてみましょう。

つまり、「すべての橋を渡る一筆書きのコースがあるか」というのは、「グラフのすべての辺を一度だけ通過するような一筆書きのコースがあるか」ということになります。

一筆書きができるための必要条件

それでは、一筆書きができるための条件を考えていきます。

いきなり「一筆書きができるグラフはどのようなものか」を考えるのは大変なので、まずは「一筆書きができるグラフにはどのような性質があるのか」を考えていきましょう。

つまり、一筆書きができるための必要条件から考えていきます。

出発点と終点が同じ場合の必要条件

適当に、一筆書きができるグラフを並べてみます。

スタートとゴールが同じグラフの場合、どこからスタートしても戻ってくることができます。
スタート地点を出発点、ゴール地点を終点、途中の点を通過点と呼ぶことにしましょう。

一筆書きができるグラフの場合、通過点に着目すると、通過点に入る辺と通過点から出る辺がペアになっています。
つまり、通過点に集まる辺の本数は必ず偶数であるはずです。

では、出発点はどうでしょう。

出発点は、最初にある1辺を通って出発します。
出発した後は通過点と同じように、通過する際には入る辺と出る辺がペアになります。
そして最終的に出発点に戻ってゴールする際に、終点＝出発点に入る辺を通ることになります。
つまり、出発点＝終点に集まる辺の本数も必ず偶数であることになります。

頂点に集まる辺の本数が偶数のとき、その頂点を「偶頂点」
頂点に集まる辺の本数が奇数のとき、その頂点を「奇頂点」と呼ぶことにすると、次のようなことが言えます。

ここで、ケーニヒスベルクの橋渡り問題のグラフを見てみると、4つの頂点がすべて奇頂点です。

つまり、ケーニヒスベルクの街には、橋を1度ずつ渡る一筆書きの散歩コースは存在しないということが分かります。

必要条件を考えることで、そのグラフが「出発点と終点が同じ一筆書きができるか」が分かるのです。

出発点と終点が異なる場合の必要条件

次に、出発点と終点が異なる場合を考えてみましょう。
先ほどと同様に、必要条件から絞っていきます。

まず通過点は先ほどと同じように、通過点に入る辺と通過点から出る辺がペアになっています。
つまり、通過点に集まる辺の本数は必ず偶数(偶頂点)であるといえます。

次に、出発点と終点を考えてみます。
出発点はまず「出る辺」が1本あり、通過する場合は「入る辺と出る辺」が2本ずつ追加されていきます。
同様に終点も、通過する場合は「入る辺と出る辺」が2本ずつ追加され、最後に「入る辺」が1本追加されて一筆書きが終了します。
つまり、出発点と終点に集まる辺の本数は必ず奇数(奇頂点)であるといえます。

まとめると、次のようになります。

一筆書きができるための必要条件

この2つの事実をまとめると、次のようになります。

しかし、この段階ではまだ必要条件に過ぎません。

つまり、この条件を満たさないグラフは絶対に一筆書きができないが、条件を満たすすべてのグラフが一筆書きができるとは限らないということです。

条件を満たすすべてのグラフが一筆書きができるならば、これは必要条件ではなく必要十分条件になります。

一筆書きができるための必要十分条件

それでは、この必要条件を満たすすべてのグラフが本当に一筆書きができるのか…
つまり、この条件は必要十分条件なのかを考えていきましょう。

出発点と終点が同じ場合の必要十分条件の証明

まずは出発点と終点が同じ場合の必要十分条件を考えます。
この場合の必要条件は、次の通りでした。

今回は逆に、

すべての頂点が偶頂点ならば、一筆書きができるということを証明します。

グラフから任意の点を1つ選び、そこから出る辺を自由に選びます。
そして思いのままに辺と頂点をたどります。
辺は有限個なので、いつかは行き詰まるはずです。
しかしすべての頂点は偶頂点なので、「入る辺と出る辺」がペアになっています。
つまり行き詰まる頂点は、最初に1本を消費した出発点です。
ゆえに、この一筆書きの経路は必ず出発点に戻ってきます。
この経路を \(S_{1}\) としましょう。

もしこの段階ですべての辺を通過していたら、それが求める一筆書きです。

すべての辺を通過していない場合は、残りの辺からつくられるグラフを考えます。

すると、この残りの辺からつくられたグラフもすべて偶頂点です。
ゆえに、\(S_{1}\) のある頂点 \(P\)から出発して戻ってくる経路 \(S_{2}\) が必ず存在します。

そして、この2つの経路 \(S_{1}\) と \(S_{2}\) を合体させます。

まずスタートして経路 \(S_{1}\) をたどり、頂点 \(P\) にたどり着きます。
そこから経路 \(S_{2}\) をたどり、頂点 \(P\) に戻ってきます。
そして経路 \(S_{1}\) の残りの部分をたどると、新しい経路 \(S_{3}\) が完成します。

この段階で、すべての辺を通過していたら、それが求める一筆書きです。

もし通過していなければ残りの辺からつくられたグラフを考えて、経路 \(S_{3}\) 上のある頂点 \(Q\) から出発して戻ってくる経路 \(S_{4}\) をつくって合体させて‥‥‥

と続けていけば、グラフの辺は有限個なのでいつかはすべての辺を通過する一筆書きが完成します。
(証明終わり)

これで、さきほどの条件が必要十分条件であることが分かりました。

出発点と終点が異なる場合の必要十分条件の証明

次に、出発点と終点が異なる場合の必要十分条件を考えます。
この場合の必要条件は、次の通りでした。

先ほどと同じように、逆に

2つの頂点が奇頂点で、残りすべての頂点が偶頂点ならば、一筆書きができるということを証明します。
この証明では、上で示したすべての頂点が偶頂点であるならば一筆書きができるという性質を利用します。

奇頂点が2つあるグラフを用意します。
この2つの奇頂点を \(P\) 、\(Q\) とします。

まず、この2つの奇頂点 \(P\) 、\(Q\) の間に辺を1本通します。
（それまでの辺と立体交差しても構いません。）
すると、このグラフはすべての頂点が偶頂点になります。

そうすると先ほどの証明から、この新しいグラフは出発点と終点が同じ一筆書きができるということが分かります。

この一筆書きの経路は循環しています。
そこで新しく加えた辺を取り除くと、2つの奇頂点を結ぶ一筆書きの経路が完成するのです。

これで、2つの頂点が奇頂点で残りすべての頂点が偶頂点であるグラフはすべて一筆書きができることが証明できました。
(証明終わり)

一筆書きができるための必要十分条件

これらをまとめると、次のようになります。

これを踏まえて、最初の例題を見てみましょう。
偶頂点に赤丸●、奇頂点に青丸●をつけるとよく分かります👇

[ウ]のグラフは、すべて偶頂点です。
つまり、どの頂点からスタートしても、戻ってくる一筆書きができることが分かります。

また[ア][イ][エ]のグラフは、奇頂点が2つあります。
つまり、1つの奇頂点からスタートして、もう一方の奇頂点でゴールするような一筆書きができることが分かります。

必要十分条件があると、実際にやってみなくても簡単に一筆書きができるか判断することができるのです。

一筆書きの経路をオイラー路、オイラー回路と呼ぶ

1736年に数学者オイラーは、「ケーニヒスベルクの橋渡り問題は不可能である」ことを証明しました。
しかし、一筆書きができるための必要十分条件までは証明できなかったようです。

今回紹介したように、グラフのすべての辺を1度だけ通る経路をオイラー路といい、特に1周して戻ってくる経路をオイラー回路とよびます。

まとめ：一筆書き問題は、実は簡単に解ける

いかがでしたでしょうか。

今回紹介した一筆書きができる条件を知っていれば、頂点が偶頂点か奇頂点かを調べるだけで簡単に一筆書きができるのか判断できます。

今までは「とにかく書いてみて、見つかれば一筆書きができるけど、見つからなければ “多分” できない」という考えだったと思います。
もし一筆書き問題を解く機会があれば、ぜひ奇頂点の数を数えてみてください。
奇頂点が0個か2個ならば一筆書きができて、1個または3個以上あれば一筆書きができません。

最後まで読んでいただき、ありがとうございました！

質問やご意見、ご感想などがあればコメント欄にお願いします👇