人気ブログランキング | 話題のタグを見る

この橋、二度渡るべからず

 「ケーニヒスベルグの問題」として有名ですが、一筆書きができる図形というのは決まっています。すなわち、奇数本の線が刺さる頂点・交点を「奇点」とし、偶数本の線が刺さる頂点・交点を「偶点」としたとき、奇点の数が0個か2個の図形の場合にのみ、一筆書きができます。

 というのも、一筆書きができるとすると、通過途中の頂点・交点は必ず「入る線」と「出る線」があるので偶点になるからです。そのため、出発点と終着点が同じとき(奇点が0個のとき)と、出発点と終着点が別々のとき(奇点が2個のとき)だけが、一筆書きできる図形です。つまり、もっとも単純で典型的な一筆書きできる図形というのは「△」と「-」です。
by kourick | 2005-09-02 00:00 | 日記