gm learning

一筆書き必勝法

　下のアプレットでは，お馴染みの一筆書きの実験ができます． グラフを描いてから，[判定]ボタンをクリックしてみましょう．

　グラフが一筆書き可能なときには， グラフ全体が薄くなります． でも，よく見ると，いくつかの辺に四角いマークが付いているはずです． そのマークされている辺の１つを選んで，クリックしてください．

　すると，その辺が青くなって，また別の辺にマークが付きます． また，マークされている好きな辺を選んでクリック． これを繰り返していくと， 青い部分がだんだん増えていって， 一筆書きが完成します．

　一方，一筆書きができない場合には， ブラウザの下の方に，一筆書きが不可能な理由が表示されます． さらに，次数が奇数の頂点が白抜きになって，マークされます．

1. グラフが非連結である．
2. 次数が奇数になっている頂点が４個以上ある．

　ということは， 入って出て，入って出てが繰り返されるのだから， その頂点に接続している辺は２本ずつ組にできるわけです． つまり，辺の本数は偶数になることになり，その頂点の次数は偶数です．

　こう考えると， グラフが一筆書きが可能ならば， 次数が奇数になる可能性があるのは， 書き始めと書き終わりの頂点だけです． つまり，奇次数の頂点があっても，２個までです． さらに，奇次数の頂点があれば偶数個という原則があるので， ２個までという条件が満たされなければ，奇次数の頂点は４個以上あることになります．

• グラフが一筆書き可能となる条件を考えたい．
• 一筆書きの次の１手を見極めるための奥義を伝授してほしい．