■ルジンの問題と電気回路(その7)

ルジンの問題とは、ひとつの正方形を、整数の辺をもつ、等しくない正方形に分割するでる。ルジン自身もこの問題は簡単に解けないと思っていたようである。

実際に多くの人が挑戦を始めたが、長方形の正方形分割のようなニアミス解しか得られなかった(例えば、32x33の長方形を9個の大きさの異なる正方形に分割する)。

この問題は多くのアタックによく耐えたので、解答することが不可能と広く信じられていた。だから、回路理論に基づいた最初の解答が現れた時には大変な騒ぎとなった。

===================================

【5】ハミルトン閉路

グラフの同じ辺を2度通らずにすべての頂点をめぐることのできる路をハミルトン路というのですが,与えられたグラフに対してハミルトン閉路が存在するのか否かを決定する一般的な基準を見つけることはグラフ理論の中でも最も難しい問題のひとつです.タットは,たとえば,4連結な平面グラフはつねにハミルトン閉路をもつ.3連結,3次正則でかつハミルトン閉路をもたない平面グラフの知られている最小の次数は46であるとかを彼は示した.

[1]ハミルトン閉路をもたないグラフで,頂点をひとつ取り除いた部分グラフもハミルトン閉路をもつ最小次数のものはペテルセングラフである(最小次数10).ペテルセングラフは五角形とその内側にある星形五角形を結んだ形として描かれることが多い.

[2]4連結なグラフはいつでもハミルトン閉路をもつ

[3]3次正則3連結でかつハミルトン閉路をもたない,知られている平面グラフの最小次数は46である.

[4]3次正則5辺連結でかつハミルトン閉路をもたない,知られている平面グラフの最小次数は44である.

[5]単純凸多面体,すなわち,どの頂点次数も3のとき,頂点の数が28以下であればハミルトン閉路をもつ(立方体,切頂八面体,正十二面体など)

[6]単純多面体でかつハミルトン閉路をもたないことが知られている多面体の最小頂点数は38である.

===================================