一筆書き                                戻る

 図形上のある点を出発して、描いた線と交わってもよいが線は共有しないという条件で、
ある図形が連続な曲線で描かれるとき、その図形は一筆書き可能と言われる。

 次の2つの図形

             

において、左図のものは一筆書き可能であり、右図のものは一筆書き不可能である。

 図形がいつ一筆書き可能かについては、次の定理が知られている。

定理  線の端点および線と線の交点のうち、奇数本の線が出ている点を 奇点,偶数
    本の線が出ている点を偶点という。このとき、図形が一筆書き可能であるために
    は、次の何れかが成り立てばよい。
 (1) 奇点の個数が、ちょうど 2 である。
 (2) 偶点ばかりである。

 この定理によれば、上図の左側の図形は奇点がちょうど2個あるので一筆書き可能で、
右図の方は奇点が4個なので一筆書き不可能となる。

 一筆書きについて数学的に考えた人としては、オイラーが有名である。「ケーニヒスベル
クの橋」という問題のことを知っている方は多いことと思う。この問題を契機として、数学は
質的な変化を遂げたと言われる。

 それまでの数学は、長さ・面積・角の大きさといった量の概念が問題であったが、一筆書
きの問題は、点同士がどのようにつながっているかという位相の概念が問題の中心になっ
ている。

 一筆書き可能かどうかについては上記の定理があるので、さらなる進展にはあまり興味
がない。

 このページでは一筆書き可能な場合に、その場合の数を求める方法について考察しよう
と思う。

 たとえば、冒頭の図
               

において一筆書きをする場合、一体いくつの場合の数があるだろうか?

 出発点がAであれば、終着点はBとなり、出発点がBであれば、終着点はAとなる。

出発点がAのとき、「A→B」の道の選び方は3通りあり、次に、「B→A」の道の選び方は2
通り、最後に、「A→B」の道の選び方は1通りあるので、この場合の一筆書きの方法の数
は、3×2×1=6(通り) となる。出発点がBのときも同様なので、したがって、求める場
合の数は、6+6=12(通り) となる。

 上記の計算から直ぐ分かるように、AとBを結ぶ線が n 本あれば、一筆書きの方法の数
は、n!×2(通り)ある。

 この問題を少し難しくしたものとして、次のような問題が考えられる。

        

 上記の図形も奇点が2個なので一筆書き可能である。その方法は何通りあるだろうか?

 出発点をAとする。このとき、「A→C」の道の選び方の場合は、

      A→B→A→B→C→B→C  、  A→B→C→B→A→B→C

の2つの場合しかない。

 よって、 3×2×1×3×2×1+3×3×2×2×1×1=36+36=72(通り)

 出発点がCの場合も同様で、求める場合の数は、 72+72=144(通り)となる。

 今度は、次の図形ではどうだろうか?

   

 出発点をAとする。このとき、「A→D」の道の選び方の場合は、

 A→B→A→B→C→B→C→D→C→D  、  A→B→C→B→A→B→C→D→C→D

 A→B→A→B→C→D→C→B→C→D  、  A→B→C→D→C→B→A→B→C→D

の4つの場合しかない。

 よって、その場合の数は、

3×2×1×3×2×1×3×2×1+3×3×2×2×1×1×3×2×1
  +3×2×1×3×3×2×2×1×1+3×3×3×2×2×2×1×1×1
=216+216+216+216=864(通り)となる。

 出発点がDの場合も同様で、求める場合の数は、 864+864=1728(通り)となる。

 今までの計算結果をまとめてみよう。

        
円の個数 ・・・
一筆書きの方法の数 12 144 1728 ・・・

 この表を眺めていると、円の個数が1増える毎に、一筆書きの方法の数が12倍に増え
ていることに気がつく。

 よって、円の個数が n 個のとき、一筆書きの方法の数は、

             12×12n−1=12(通り)

であることが予想される。果たして、この予想は正しいのだろうか?

 この予想が正しいことを数学的帰納法で示そう。

n=1 のとき、 6+6=12(通り)で成り立つ。

n=k(k≧1)のとき成り立つと仮定する。

 n=k+1 のときの道の選び方の数は、

    1個の円+k個の円 または k個の円+1個の円 の道の選び方の数

に場合分けすることができる。ただし、この場合、

「A→B→・・・→C→D→C→・・・→B→A→B→・・・→C→D」のような道の選び方の数と

「A→B→A→B→・・・→C→D→C→D」のような道の選び方の数は等しいことに注意する。

 このとき、 (3!×(12÷2)+(12÷2)×3!)×2=12k+1(通り) となる。

よって、n=k+1 のときも成り立つ。

 以上から、全ての自然数 n に対して、求める場合の数は、12(通り) である。


 当HPがいつもお世話になっているK.S.さんから、平成24年4月10日付けメールで「オ
イラーの一筆書きの定理の拡張」についてのレポートを頂いた。(平成24年4月22日付け)

 オイラーの一筆書きの定理の拡張

(1) 奇数点が0個のとき、全ての点から一筆書きが可能でサイクルをつくる。
(2) 奇数点が2個のとき、ある奇数点から始めて、他の奇数点で終わる一筆書きが可能。
(3) 奇数点が2n個(n>1)のとき、一筆書きは不可能。但し、n回で可能。
(4) 奇数点が、奇数個のグラフは存在しない。

 (1)(2)については、よく知られています。(3)について、2n個の奇数点どうしを、2個の
奇数点を残して奇数点どうしを結ぶと(2)になり、したがって、残った奇数点から始めても、
一筆書きが可能になります。よって、間に追加したn−1個の線を通ったのですが、通らな
かったことにすれば、n回で全ての点を通ることができます。(4)について、各点における
辺の個数をすべて足し合わせると総和は偶数になります。なぜなら、一つの辺は2度づつ
数えられているからです。一方、奇数点が奇数個あると総和が奇数となり矛盾します。

 オイラーの多面体定理の拡張(辺で連結した単体)(予想)

 平面図形のとき、 V(点)−E(辺)+F(面)=1

 凸多面体のとき、V(点)−E(辺)+F(面)=2

 一つにまとめて、更に、胞が複数、曲線、面(膜)が欠いている場合(凹型)も含めて考えて
みました。

  V(点)−E(辺)+F(膜)―C(胞)=f−r+P−R

が成り立つ。ここで、直観的に、

  C=胞(膜に囲まれた部分)の独立した個数

  f=連結した膜(点または辺で隣り合う)の独立した個数

  r=小さい輪(一つの辺に一つかけ、はずれない)の個数
    膜がない辺のときは、必ず小さい輪を持つ

  P=要の点(膜を持たない頂点)の個数

  R=大きな輪(膜に囲まれた一つの穴に一つかけ、はずれない)の個数

 これらを、ご検証ください。

例1 立方体の、上と下の膜のみを欠いたとき、 V(8)−E(12)+F(4)−C(0)=0

 一方、右辺は、 f(1)―r(0)+P(0)―R(1)=0

例2 立方体の、上と下の膜のみを残したとき、 V(8)−E(12)+F(2)−C(0)=−2

 一方、右辺はf(2)―r(4)+P(0)―R(0)=−2

例3 立方体の、隣り合う3つの膜を残したとき、 V(8)−E(12)+F(3)−C(0)=−1

 一方、右辺はf(1)―r(3)+P(1)―R(0)=−1

注:立体を平面化しても、標数は不変だが、数え方(f,r,R,P)に変化がある。平面の形を
  三角形に限定し、Fについての帰納法で証明する。

 平面の直線による分割について、

   平面の分割数=1+(直線の個数)+(交点の個数)

 但し、交点の個数=n重点のとき、n−1個とする。

これを、ご検証ください。

 オイラーの定理から導くことができる。

 全ての交点を十分に含む大きな円を考えることができるので、直線による円の内部の面
の分割数と同じと考えてもよい。(以下の交点数は通所の意味です)

 そこで、交点の間を辺と考えて、平面グラフなので、

  V(交点の数)−E(辺の数)+F(分割された面数)=1

 ここで、円周上の点とその点に分けられた辺は同じ数あるので、相殺されて、

  V(円の内部の交点数)−E(円の内部の辺数)+F(分割された面数)=1 ・・・ (1)

が成り立たちます。各直線ごとに、 1=(その直線上の辺数)−(その直線上の交点数)が
成り立つので、円内にある全ての直線の本数をLとして、

 L=Σ(直線の辺数)−Σ(直線上の交点数)  (Σは全ての直線による和)

 直線上の辺は、各直線ごと別々に存在しているので、

 E(円の内部の辺数)=Σ(直線の辺数)

 直線上の交点は、重複しているので、r 個の直線によってできた交点の数を、P とおく。

 V=P2+P3+・・・+P 、Σ(直線の辺数)=2P2+3P3+・・・+rP

 L=E−(2P2+3P3+・・・+rP) より、 E=L+(2P2+3P3+・・・+rP

 これらを(1)に代入すると、

 (P2+P3+・・・+P)−{L+(2P2+3P3+・・・+rP)}+F(分割された面数)=1

 よって、 F=1+L+P2+2P3+・・・+(r−1)P より、

    F=1+L(直線の辺数)+P(r重交点をr−1個として数えた数の和)

 球面の直線による分割について

  球面の分割数=2+(交点の個数)

 但し、直線は大円を意味する。交点の個数は、n重点のとき n−1個とする。

(証明) オイラーの多面体定理より、凸立体なので、V−E+F=2 より、F=2+E−V

  r 個の直線によってできた交点の数を、P とおくと、 V=P2+P3+・・・+P と分ける

 ことができる。辺は、点P に対して、2r本がつながり一つの、辺の両端に点があるので、

  E=(4P2+6P3+・・・+2rP)÷2=2P2+3P3+・・・+rP

 このとき、 E−V=P2+2P3+・・・+(r−1)P

 つまり、 F(平面の数)=2+(交点の数)  (証終)


(追記) 当HPがいつもお世話になっているHN「GAI」さんが一筆書きの話題を投稿されま
    した。(平成27年5月9日付け)

   左図を見ると、一筆書きがやってみたくなる。
   (奇点が2つなのでOK)

   さて、一筆書きできる書き順は何通り?



 また、次の場合には何通りになる?

 


 らすかるさんが考察されました。(平成27年5月9日付け)

 最初の2連の場合は、端の線分の取り方で分類すると、(ちょっとわかりにくいですが)

「−日−」型が4通りでそれぞれ経路は6個 、「>◇◇」型が4通りでそれぞれ経路は4個
「◇<_>◇」型が1通りで経路は4個

なので、 4×6+4×4+1×4=44通り となりますね。

 次の5連の場合は考えるのが大変そうなので、とりあえずプログラムで数えました。

1連:6通り
2連:44通り
3連:328通り
4連:2448通り
5連:18272通り
6連:136384通り
7連:1017984通り
8連:7598336通り
9連:56714752通り
10連:423324672通り  そして、この数列は、「A102591」にありました。

 a[0]=1、 a[1]=6、 a[n+2]=8a[n+1]-4a[n] という漸化式で表せるようです。


 GAI さんからのコメントです。(平成27年5月9日付け)

 うまく読み取れないので理由はわかりませんでしたが、私は馬鹿正直に見落としと、重複
が無いかを点検しながら、44通りのルートを作り出しました。これ以上でも、これ以下でもな
いことを保証できます。

 実際には、出発点と到着点の入れ替えも可能なので、2×44=88(通り)ですよね。

 また、連にしないでも、奇数個の正三角形の図形では、

  a[0]=1、 a[1]=2、 a[n+2]=2a[n+1]+2a[n]

なる漸化式が構成でき、

a[2]=6
a[3]=16
a[4]=44 (実質、2連図形)
a[5]=120
a[6]=328
a[7]=896
a[8]=2448
a[9]=6688
a[10]=18272 (実質、5連図形)
・・・・・・・・・

より、10個の5連図形では一筆書き 2×18272=36544(通り) となり、一日で100通りの行き
方を書いていっても1年では書き切れないパターンが存在する。(→参考:「A002605」)

 この漸化式を考え付く発想力はとても浮かぶ余裕がない。また、この一般項a[n]が

a[n]=((1+√3)^(n+1)-(1-√3)^(n+1))/√3

で表せるなんて思いもよらない。これに興味を抱いたので、今度は正方形の辺どうしをつな
げた図形で一筆書きが可能なものを探すことをやってみました。

ドミノ   (正方形が2つつながる図形) 1種類中 1(個)
トリオミノ(正方形が3つつながる図形) 2種類中 1(個)
テトロミノ(正方形が4つつながる図形) 5種類中 2(個)
ペントミノ(正方形が5つつながる図形) 12種類中 2(個)
ヘキソミノ(正方形が6つつながる図形) 35種類中 6(個)
ヘプトミノ(正方形が7つつながる図形) 108種類中 4(個)
オクトミノ(正方形が8つつながる図形) 369種類中 17(個)

 どこかに見落としや、勘違いがあるような恐れもありますが、何方か間違いがあれば御指
摘ください。


 らすかるさんからのコメントです。(平成27年5月10日付け)

 一筆書き可能について調べました。私のプログラムが正しければ、

ペントミノは、12種類中 3個
ヘプトミノは、108種類中 8個
オクトミノは、369種類中 18個

になると思います。ペントミノはF型、W型、X型の3個が一筆書きできますね。

F 型 W 型 X 型

 また、オクトミノの先は、

ノノミノ(正方形が9個つながる図形):1285種類中 28個
デコミノ(正方形が10個つながる図形):4655種類中 60個
ウンデコミノ(正方形が11個つながる図形):17073種類中 102個
ドデコミノ(正方形が12個つながる図形):63600種類中 206個
13-オミノ(正方形が13個つながる図形):238591種類中 380個
14-オミノ(正方形が14個つながる図形):901971種類中 752個
15-オミノ(正方形が15個つながる図形):3426576種類中 1399個

でした。


 GAI さんからのコメントです。(平成27年5月10日付け)

 へ〜プログラムで調べることができるんですね。凄い!こんな調査にはこの力がないと到底
及ばないですね。

 ペントミノは奇点2個ばかり気を取られていて、偶点のみのXを落としていました。
(またうっかり癖が出ました。)

 ヘプトミノは4個も見落としていたなんて、私の目は節穴に近い。

 オクトミノは17までは見つけていたんですが、18と聞いて再び探すもなかなか見つけられず
やっとの事で最後の1つを発見できました。

 これも18個あるという情報があればこそできることで、ないと見逃す恐れ大です。

 ここまではサイトを利用すれば具体的図形が掲載されていたので出来ますが、それ以上の
なんと15-オミノまでの結果が知れるなんて思ってもいませんでした。一体どれ位の時間を要
したんでしょうか?これを可能にするプログラムを組み上げ、一日以内でこの膨大な計算結
果を出せるなんて驚異です。プログラミンングについての長年の経験とセンスがなければ決
してできる技ではありません。私も真似たいですが、60を過ぎた身には到底無理です。老眼
を武器に地道に数えるしかありません。

 知りたかった思った以上の遥かな世界が見られて嬉しいです。


 らすかるさんからのコメントです。(平成27年5月10日付け)

 私にとっては、オクトミノの一筆書きを手作業で調べる方が「凄い!」と思います(笑)
プログラムの実行時間の大半がパターンデータを作る時間で、パターンデータがあれば一筆
書き可能かどうか調べるのはあっという間です。最終版のプログラムでは、パターンデータを
作る時間を含めて、n=10までは一瞬、11までで1秒、12までで4秒、13までで16秒、14までで
1分9秒、15までで5分50秒でした。
(9年前のPCでの実行時間ですので、最新のPCなら1〜2分だと思います。)

 ただし、高速化のためにプログラムを何度も改良していますので、プログラムの作成には
合計で2時間ぐらいかかっています。


 GAI さんからのコメントです。(平成27年5月10日付け)

 ヘキソミノ35種類中一筆書きができる図形は次の6タイプに限られる。
では、この6タイプの異なる一筆書きができる描き方の多い順に並べるとどの様になると思
いますか?

  <type1>
    ・─・
   │ │
 ・─・─・─・─・
 │ │ │ │ │
 ・─・─・─・─・
   │ │
   ・─・
  <type2>
    ・─・
   │ │
 ・─・─・─・─・
 │ │ │ │ │
 ・─・─・─・─・
     │ │
     ・─・
  <type3>
      ・─・
      │ │
 ・─・─・─・
 │ │ │  │
 ・─・─・─・─・
         │ │ │
         ・─・─・
<type4>
      ・─・
      │ │
 ・─・─・─・
 │ │ │  │
 ・─・─・─・
     │ │ │
     ・─・─・
<type5>
      ・─・
      │ │
 ・─・─・─・
 │ │ │  │
 ・─・─・─・
  │ │ │  │
  ・─・  ・─・
<type6>
 ・─・─・
 │ │ │
 ・─・─・─・
     │ │ │
     ・─・─・─・
         │ │ │
         ・─・─・




    以下、工事中