一筆書きの法則

一筆書きの法則

一筆書きができるのは図形の奇点の数が０または２のときのみである。

奇点というのは次のように辺が奇数個つながっている頂点のことです。（辺が偶数個つながっている頂点は偶点と呼びます。）

なぜ法則が成り立つのか

頂点のは始点（スタート）・通過点・終点（ゴール）の３つに分けることができます。

まずは通過点になるのはどのような頂点なのか考えてみます。

通過点になる頂点は必ず偶点ということができます。

理由は簡単で、点を通過すると２本の辺を追加することになるので、その点を何回通過しても増える辺は偶数本ということになります。

通過点は必ず偶点。

始点・終点に関して、次の２パターンで状況が変わります。

始点と終点が一致している場合、その点は偶点になります。

まず始点から出発したときには辺は１本。

そこから何回か通過しても辺は２本ずつ増えるので辺の数は奇数本になります。

さらに終点としてゴールすると１本辺が追加されるので最終的な辺の数は偶数本になります。

始点と終点が一致している場合、その点は偶点になる。

始点と終点が一致していない場合、始点・終点はそれぞれ奇点になります。

頂点が始点のときは先程考えた「始点と終点が一致している場合」から終点の役割を除けば良く、最終的に奇点のままであることがわかりますね。

終点も同様に奇点になります。

始点と終点が一致していない場合、それぞれの点は奇点になる。

よって奇点は始点か終点にしか使えないため、奇点の数は０か２になるというわけです。

図形の頂点がすべて偶点の場合は、どこにも行き止まりがないことになります。

なので次の図のように必ず閉路（一周の輪っか）が存在します。

ここで、この閉路を取り除いた図形を考えると、これもまた偶点のみの図形になっています。

これを繰り返していくと、偶点のみの図形はいくつかの閉路で構成されていることがわかります。

これさえ分かれば、閉路を通るついでに他の閉路も回収、そのときにまた他の閉路があれば回収…というのを続けていけば一筆書きができるという仕組みです。

奇点が存在する場合はその点は必ず始点か終点として使います。

まずは奇点から奇点に向かいます。

するとのこりはすべて偶点になるので、あとはすべて偶点の場合と同様にすれば一筆書きを完成させることができます。