No.4ベストアンサー
- 回答日時:
次のように考えたらいかがでしょうか。
仮に与えられたグラフについて、一筆書きが可能だとすれば、最短距離の経路はその一筆書きであることは明らかです。
一筆書きが可能なグラフは、すべての点についてその点を通る線分の数が偶数であるか(これを偶点と呼ぶことにします)、その点を通る線分の数が奇数の点(これを奇点と呼ぶことにします)が2つだけ存在するかです。前者の場合はすべての点について、その点を出発してその点に戻る一筆書きが可能ですが、後者の場合、可能な一筆書きは一方の奇点を出発してもう一方の奇点に戻るルートだけです。
しかし、問題のグラフには奇点がB、C、D、Xと4つ存在しますので、このままでは一筆書きはできません。またXを出発してXに戻るルートが指定されています。
そこで、奇点どうしを結ぶ線分を付け加えてその2点の間は往復してもよいことにし、すべての点を偶点にできれば、Xを出発してXに戻る”一筆書き”が可能です。
問題のグラフでは、奇点が4つなのでこの線分は最低2本必要ですが、求める"一筆書き"の経路を最短にするには、線分を付け加える2点間の距離ができるだけ短い2点を選ぶ必要があり、それはBC間(10m)とDX間(12m)です。
求める最短距離の経路はこのBCとDXを2回通るルートで、お礼に書かれたX→B→A→X→C→B→C→D→E→X→D→Xもその一つで、最短距離は136mです。
もちろん最短距離の経路はこれに限らず、例えばX→C→D→X→B→C→B→A→X→E→D→X なども条件を満たしますが距離はいずれも136mです。
No.3
- 回答日時:
No.2
- 回答日時:
片方の四辺形で考えれば簡単じゃないの ?
四角形X-C-B-Aで最短で戻るには、B-Xの部分が重複(=往復)されて元に戻れるんじゃない ?
詰まり、X→B→A→X→C→B→Xの場合だったら、B-X 部分、往復することになる。
もう一つの四角形X-C-D-Eも同じく考えて、D-Xが重復
2っつの四角形が合わさりますので、C-X部分が重複
詰まり、重複部分は3箇所在り、B-X、D-X、C-Xの部分。
従って、Xを出発して再びXに戻って来る為には、
(X-A)+(A-B)+(B-C)+(X-E)+(D-E)+(C-D)+2(X-B)+2(X-D)+2(X-C)=8+17+10+11+14+13+2×15+2×12+2×14
=155 m
四角形の場合、最短で戻るには、出発地点を含む対角線部分が重複されて、元に戻れるんでないかい ?
ご解答ありがとうございます。
私の場合は
X→B→A→X→C→B→C→D→E→X→D→X
あわせて
15+17+8+14+10+10+13+14+11+12+12=136m
なりますが...
No.1
- 回答日時:
>X を出発して、すべての道を 1回以上通って
>直感で8+17+10+13+14+11=73になるかと思いますが
すべての道を1回以上通っていますか?
ご指摘、ありがとうございます。
すべての道を 1回以上という文言に気づきませんでした。
失礼しました。
そうしたら私のやったところ
X→B→A→X→C→B→C→D→E→X→D→X
あわせて
15+17+8+14+10+10+13+14+11+12+12=136m
なりますが、合っていますか。これもやはり直感です。
何かこの手の問題を解くために共通のやり方ってありますかな。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- タクシー タクシーの運賃ってなぜJRのような大都市近郊区間のような最短経路の運賃計算にしないのですか? 実際の 7 2023/06/27 11:30
- 数学 問題:点Aから点Bまでの最短経路は全部で何通りあるか。ただし、斜線部分は通れないものとする。 解説: 4 2023/02/24 11:44
- 自転車保険 【労務事務】従業員の通勤経路について 5 2022/10/06 09:34
- 大学・短大 電子回路の問題 2 2022/12/11 14:56
- 高校 「高校生クイズ。 何問目」。「2問目」です。「回答(解答)」をお願い出来ますか? 理解出来ません。 1 2022/04/17 13:44
- その他(職業・資格) 資格試験の過去問 1 2023/07/13 16:34
- 数学 一次関数の最短距離の問題です。 A(4,3)B(0,2)がある。x軸上にAP+PBが最短となるように 3 2022/12/16 01:12
- 高校受験 数学の問題いくつか捨てても大丈夫?残り1ヶ月、点数が取れない教科ばっか勉強しても大丈夫? 高校受験 2 2023/01/07 17:55
- 数学 【 数I 2次関数の文章題 】 問題 ※写真 解答(先生作) t秒後にはPB=10-t,BQ=2tと 2 2022/06/28 17:40
- 建築学 ネットワーク工程表(1級管工事施工管理) 5 2022/08/24 08:17
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
3次元空間上の2点を結ぶ線分の...
-
方冪の定理の演習問題
-
三点の座標から中心点の求め方
-
ベクトルの問題。解説お願いし...
-
直角二等辺三角形の書き方教え...
-
折戸の軌跡
-
spi 非言語教えてください
-
凸とstarlikeの違い
-
ベクトルと平面図形の問題です。
-
正四面体の問題
-
x²+y²=2と y=x+kが異なる2...
-
AB=2,BC=3,∠ABC=60°の三角形が...
-
電験の参考書でわからなくて困...
-
数学A 三角形の内心の問題です
-
ベクトルについて。
-
A(-4,2,1)、B(6,-4,5)とすると...
-
数学を教えてください
-
数学Aの外分がわかりません。 ...
-
作図の問題
-
有限と無限の違いは何なのでし...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
ベクトルの問題。解説お願いし...
-
円が直線から切り取る線分の長...
-
外心と内心、もしくは重心と外...
-
有限と無限の違いは何なのでし...
-
ある点からある直線へ降ろした...
-
組み合わせ
-
直角二等辺三角形の書き方教え...
-
至急です!お願いします! 図の...
-
3次元空間上の2点を結ぶ線分の...
-
2線分の最短距離
-
正三角形でない△ABCの重心G,外...
-
正四面体の問題
-
ヤングの実験で質問です。この...
-
数学のベクトルの問題です。 四...
-
TeXのmawarikomi環境について
-
△OABに対し、OPベクトル=sOAベクトル+...
-
高校数学 文字の置き方について
-
多角形の自己交差を判定するには?
-
公務員試験の判断推理の方位の...
-
ベクトルと平面図形の問題です。
おすすめ情報