（草稿）
(2, 2)の場合 8通り
□□
□□
12 14 21 41 34 32 34 23 43
43 23 34 32 21 41 21 14 12
(1, 1)から
(+1, 0), (0, -1), (-1, 0) 計 (0, -1)
(0, -1), (+1, 0), (0, +1) 計 (+1, 0)
(1, 2)から
(-1, 0), (0, -1), (+1, 0) 計 (0, -1)
(0, -1), (-1, 0), (0, +1) 計 (-1, 0)
(1, 2)から
(0, +1), (+1, 0), (0, -1) 計 (+1, 0)
(+1, 0), (0, +1), (-1, 0) 計 (0, +1)
(2, 2)から
(0, +1), (-1, 0), (0, -1) 計 (-1, 0)
(-1, 0), (0, +1), (+1, 0) 計 (0, +1)
(3, 2)の場合 16通り
□□□
□□□
123 165 145 612 216 561 541 321
654 234 236 543 543 432 632 456
456 632 432 345 543 234 236 654
321 541 561 216 612 165 145 123
(3, 3)の場合 40通り
□□□
□□□
□□□
123 123 123 129 | 187 189 167 145
894 874 654 438 | 296 276 258 236
765 965 789 567 | 345 345 349 987
(x4)
923 329 | 789 543 | 567 765 | 345 987
814 418 | 612 612 | 418 814 | 216 216
765 567 | 543 789 | 329 923 | 987 345
1. 行き止まりが3つ以上あるグラフは一筆書きできない
(行き止まりとは、繋がっている点が1つしかない点)
e. g.
□□□
□
【問1】
行き止まりが3つ以上あるグラフを一筆書きできないのは何故か。
【問2】
点1つのみのグラフを一筆書き可能とするか。
【問3】
(3, 3)のグラフで(2, 1), (1, 2), (2, 3), (3, 2)始点の一筆書き不可能なのは何故か。
【問4】
任意の正則グラフで、一筆書きできるパターンの数をどう計算するか。
【問5】
(5, 5)のグラフで(3, 2), (2, 3), (3, 4), (4, 3)始点の一筆書き不可能なのは何故か。
【問6】
任意のグラフで一筆書き不可能な始点が存在することはどのように分かるか。
【問7】
KAERU JUMP（
http://www.gamedesign.jp/flash/kaeru/kaeru_jp.html）の解法は何か。
行き止まりとは、隣り合うノードが1つ以下であるノード。
Tグラフとは、行き止まりが3つ以上あるグラフ。
1. Tグラフは一筆書き不可能
2. グラフGから始点xを除いたグラフG'がTグラフであるとき、グラフGにおいて始点xからの一筆書きは不可能
3. グラフGから始点xを除いたグラフG'に行き止まりが2つ以上あるとき、グラフGにおいて始点xからの一筆書きは不可能
4. 隣り合うノードが無いノードが存在するグラフは、一筆書き不可能
【問8】
Tグラフであることは、一筆書き不可能であることと同値か。
(4, 3)の場合 ?通り
□□□□
□□□□
□□□□
1234 1234 1234 123c 12ba 12bc 129a 1256
abc5 c985 8765 654b 43c9 43a9 438b c347
9876 ba76 9abc 789a 5678 5678 567c ba98
1a98
2bc7
3456 (中断)
3. グラフGから始点xを除いたグラフG'に行き止まりが2つ以上あるとき、グラフGにおいて始点xからの一筆書きは不可能
誤り
反例：
□□□
[1, 1]を除くと[2, 1]と[3, 1]が行き止まりになり、行き止まりが2つ以上になるが、[1, 1]からの一筆書きは可能なグラフ
5. グラフGから始点xを除いたグラフG'が、行き止まりのないグラフであるとき、グラフGにおいて始点xからの一筆書き可能
反例：
□□ □□
□□□□□
[3, 2]を除いても行き止まりは増えないが、[3, 2]からの一筆書きは不可能なグラフ
グラフの拡張
三角グラフ
＿＿
／＼／＼
￣￣￣￣
六角グラフ
／＼／＼
| | |
／＼／＼／＼
＼／＼／＼／
| | |
＼／＼／
トーラス
□□□
□ □
□□□
終点には偶奇性がある。
☆＝始点 ●＝終点 ■＝可能終点
2x2
☆■
■□
→↓ ↓●
●← →↑
3x2
☆■□
■□■
↓●← ↓→↓ →→↓
→→↑ →↑● ●←←
3x3
☆□■
□■□
■□■
↓↓← ↓→● ↓→↓ ↓→↓
↓●↑ ↓↑← ↓↑↓ →↑↓
→→↑ →→↑ →↑● ●←←
☆＝始点 ★＝可能始点 ●＝終点 ■＝可能終点
☆■□
■ □
□□□
□☆□■□
□ □ □
□■□■□
□□□□□
□ □ □
□□□□□
□ □ □
□□□□□
★□★
□★□
★□★
★★★★★
★★□★★
★□★□★
★★□★★
★★★★★
□□□□□□□
□□□□□□□
□□□□□□□
□□□□□□□
□□□□□□□
□□□□□□□
□□□□□□□ ?
★★
★□★
□□□
□
★□★
□★
★★
★★
★★★
★★★
★★★★
★★★★
★★★★
★★★★
★★★★
★★★★
★★★★
【問9】
□ □
□□□
□□□
が一筆書き不能グラフなのは何故か。
【問10】
グラフGから、不可能始点xを除いたグラフG'は、一筆書き不能か。
【答9】
偶数目と奇数目の数の差が2以上あるから。
■＝偶数目 □＝奇数目
（一筆書き不能なグラフ）
■ ■
□■□
■□■ 偶数目：５ 奇数目：３
（一筆書き不能なグラフ）
■□■
■ 偶数目：３ 奇数目：１
（一筆書き不能なグラフ）
■□■□■
□ □ □
■□■□■
□ □ □
■□■□■ 偶数目：９ 奇数目：１２
III. 偶数点と奇数点の差が2以上あるグラフは、一筆書き不能。
5x5の場合、加えて
[2, 1], [4, 1], [2, 1], [2, 5], [4, 1], [4, 5], [5, 2], [5, 4]も
一筆書き不能始点だった。
★□★□★
□★□★□
★□★□★
□★□★□
★□★□★
【問12】
一筆書き不能グラフはすべて、偶数ノードと奇数ノードの差が2つ以上あるのか？
反例：
□ ■
■ □
□ ■
（偶数ノードと奇数ノードの数の差が2つ未満であり、かつ一筆書き不能なグラフ）
最終更新：2015年04月29日 16:22
