|
スモークマン |
|
#27452
今回の場合、色んな条件に気付けば、対角線に対して対称のルートを含めた２通りしかないということですよね！？ 一筆書き可能かどうかの判定法(Wikipediaより) ある連結グラフが一筆書き可能な場合の必要十分条件は、以下の条件のいずれか一方が成り立つことである。 *すべての頂点の次数が偶数； 運筆が元に戻る場合(閉路） *次数が奇数の頂点の数が2で、残りの頂点の次数は全て偶数； 運筆が必ずしも元にもどらない場合（路） 今回の場合、下のケースの図を作れて、しかも、一筆書きの方法が一通りなら最短になりますね。 3x3 の正方形から、スタートを左上に、ゴールを右上にすると、上記条件を満たすように（これが試行錯誤かも・・・？）7本の線分を除けば一筆書きができる図となり、このとき、残りの線分は、3*4*2-7=17 本。 右上のゴールから右下まで動けばよいので、17+3=20 と分かる？ どう最大に除いたらそういう図になるかがまた問題で、結局あまり進歩がないか。。。(^^; |
|
金光
5月19日（金） 12:23:30
MAIL:kennji72001@yahoo.co.jp 27454 |