斜方二十・十二面体の頂点を最小数で移動する方法

質問

数学の図形の問題なのですが、
斜方二十・十二面体（構成面：正三角形20枚、正方形30枚、正五角形12枚、辺：120、頂点：60）について、ある頂点から出発し、全ての辺を通ることを考える際の、最短移動数（通過する辺の最小数）の求め方は、どのように考えればよいでしょうか？複数回同じ辺を通ると思いますが、考え方がわかりません。
全ての辺が正方形に属することから、正方形の展開図で考えてみようと思いましたが、考えかたがわからず解けない状況です。

回答No.12

178-tall · ベストアンサー

< ANo.9　への蛇足。

目算例のメモ。
　　ANo.10 の「5 角形」に頂点ごとの番号を付与して
　　ANo.3 の手で始点から終点までの頂点をたどり
　　さらに未通過の辺をたどって始点へ戻る
までの手順と、残余辺セットを記しておきます。

番号 … 外側の「5 角形」から付与していく。
　　5 角形 → てっぺんの頂点から反時計回りに、1 ～ 5
　　10 角形 → てっぺん左の頂点から反時計回りに、6 ～ 15
　　15 角形 → てっぺん左の頂点から反時計回りに、16 ～ 30
　　15 角形 → てっぺんの頂点から反時計回りに、31 ～ 45
　　10 角形 → てっぺん左の頂点から反時計回りに、46 ～ 55
　　5 角形 → てっぺん左の頂点から反時計回りに、56 ～ 60

始点 1 から終点 57 までの経路。
(以下、m～n はm から n まで番号順、他はコンマ区切り順)
　　1～5, 14, 15, 6～13, 27～30, 16～26, 42～45, 31～41, 52～55, 46～51, 58～60, 56, 57 まで

終点 57 から始点 1 まで戻る経路。
　　57, 58, 50, 38, 23, 39, 51, 52, 59. 53, 42, 41, 26, 27, 43, 28, 14, 13, 5, 1 まで

通り損ねた辺 (閉路 7 つ) の頂点セット。
　　{1, 6, 16, 31, 30, 15},　{2, 8, 19, 34, 18, 7}
　　{3, 10, 22, 37, 21, 9},　{4, 12, 25, 40, 24, 11}
　　{17, 33, 47, 56, 46, 32},　{20, 36, 49, 57, 48, 35}
　　{29, 45, 55, 60, 54, 44}

お礼

有難うございます。どうしても一筆書きが出来ないと思っていたのですが、閉路とわけて考えると分かりやすく、納得できました。どうも有難うございます。

回答No.11

178-tall

< ANo.10
…蛇足のまた蛇足。

"more images" の 「5 角形」にて、同心の 5 角形、10 角形、15 角形、15 角形、10 角形、5 角形　を除くと、10 個の孤立閉路が残る。
これで、ANo.6 に例示した "devide and rule" がやり易くなる模様。

ANo.9 の目算例は単なる "one of them" でした。

回答No.10

178-tall

蛇足。

参考URL の images にて、more images をクリックすると現れる 5 角形が使いよい。

参考URL：

http://www.wolframalpha.com/input/?i=small+rhombicosidodecahedral+graph

回答No.9

178-tall

Fleury's Algorithm を試作する元気ない…ので目算例。

　まず、ANo.3 の手で始点から終点までたどる。
　その終点から、未通過の辺をたどって始点へ戻る。

…までは、できそうです。

改めて通り損ねた辺を見ると、みな閉路 (のはず) だから、始点から終点へ向かう途中で巡回すれば、チョン！

回答No.8

178-tall

アルゴリズムの一例…。

参考URL / Fleury's Algorithm

参考URL：

http://www.austincc.edu/powens/+Topics/HTML/05-6/05-6.html

回答No.7

178-tall

>…結構めんどうそうですけど。

　　↓ 参考 URL

　　！！

参考URL：

http://mathworld.wolfram.com/SmallRhombicosidodecahedralGraph.html

回答No.6

178-tall

>…一筆書き可能であれば120なのだと思いますが、具体的にどういった手順でなぞっていけば良いかイメージがつかないです。

やはり、なぞるのですか。

たとえば 参考 URL の、
　オイラーグラフの定理の証明
　　「次数が偶数→オイラーグラフ」の証明
などが基本。

この例題じゃ、結構めんどうそうですけど。

参考URL：

http://mathtrain.jp/euler_graph

回答No.5

178-tall

>一筆書きの理論に当てはまるということは分かりました。ただ、実際に書いてみようとするとなかなか上手く行かないのですが…

　そして、

>…全ての辺を通ったうえでの最短移動数ですので、こちらのやり方では出来ないようです。

　　↓

タイトルに「頂点を最小数で移動」、文中に「全ての辺を通ることを考え…」とあり、ANo.1 なのか、ANo.4 なのかを迷ってました。
ANo.1 (全ての辺を通る) なのですね。

求めたいのは「最短移動数（通過する辺の最小数）」？

>　辺：120、頂点：60
がわかっている模様…なので、「一筆書き可」なら、120 なんじゃありませんか？

それとも…？

補足

タイトル、文中で問いがズレてしまっていました。ANo.1で間違いないです。
一筆書き可能であれば120なのだと思いますが、具体的にどういった手順でなぞっていけば良いかイメージがつかないです。

回答No.4

178-tall

>　　手前の 5 角形を一巡
>　　ひとつ奥の 10 角形へ移動
>　　10 角形を一巡
>　　もひとつ奥の 15 (？)角形へ移動
>　　…

各頂点を一回ずつ、すべて辿れそう。

ならば、「最短移動数（通過する辺の最小数）」なのだろう。

補足

有難うございます。全ての辺を通ったうえでの最短移動数ですので、こちらのやり方では出来ないようです。

回答No.3

178-tall

「全ての頂点を通ることを考え」ると…
イラスト ( ↓ 参考 URL) にて、

　　手前の 5 角形を一巡
　　ひとつ奥の 10 角形へ移動
　　10 角形を一巡
　　もひとつ奥の 15 (？)角形へ移動
　　…

…という手順など、いかが？

参考URL：

http://upload.wikimedia.org/wikipedia/commons/9/96/Rhombicosidodecahedron.jpg

補足

有難うございます。全ての頂点ではなく、全ての辺になりますので、こちらのやり方では出来ないようです。

回答No.2

trytobe

展開図だと、せっかく通った辺が別の所にも分身として存在してしまうので、一筆書きを考えるのが良いのだろうな、とは思います。

平面のときには、すべての交点が偶数本の線の合流になっているか、２ヶ所だけ奇数本の合流になっているだけで、一筆書きできる必要十分条件なので、

一筆書き - Wikipedia
http://ja.wikipedia.org/wiki/%E4%B8%80%E7%AD%86%E6%9B%B8%E3%81%8D

さて、これが立体のときにも成り立つのをどうやって示すのがいいのかな・・・、と思って、やっと、

「斜方二十・十二面体」の全部の辺がゴムひもで出来ていて、５角形の面のどれかを思いっきり広げて、他の辺が全部中に入るような形で平面にしたらいいじゃん、

斜方二十・十二面体 - Wikipedia
http://ja.wikipedia.org/wiki/%E6%96%9C%E6%96%B9%E4%BA%8C%E5%8D%81%E3%83%BB%E5%8D%81%E4%BA%8C%E9%9D%A2%E4%BD%93

と気がついて、平面のときのように、スタート地点に戻ってくるような一筆書きで、斜方二十・十二面体の１２０すべての辺をなぞれる、とわかりました。

補足

有難うございます。一筆書きの理論に当てはまるということは分かりました。ただ、実際に書いてみようとするとなかなか上手く行かないのですが、書き方としてはどういった手順になるでしょうか？