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で質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
円が直線から切り取る線分の長...
-
二等辺三角形の性質(定理)の...
-
双曲線の定義
-
数Aの証明
-
直角二等辺三角形の書き方教え...
-
中3のの図形の証明について 図...
-
TeXのmawarikomi環境について
-
数直線上で0の次は何ですか?
-
ベクトルと平面図形の問題です。
-
数学の問題で 2点A(0, 1), B(1,...
-
spi 非言語教えてください
-
数学II 直線y=2x+kが放物線y=3x...
-
至急です!お願いします! 図の...
-
ベクトルの問題。解説お願いし...
-
すいません。 ずっと計算してる...
-
3次元空間上の2点を結ぶ線分の...
-
三平方の定理を用いた三角形の...
-
数学のベクトルの問題です。 四...
-
ベクトルについて。
-
作図問題
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
これなぜせんぶんAB上だったり...
-
円が直線から切り取る線分の長...
-
直角二等辺三角形の書き方教え...
-
2線分の最短距離
-
ベクトルの問題。解説お願いし...
-
ある点からある直線へ降ろした...
-
至急です!お願いします! 図の...
-
TeXのmawarikomi環境について
-
組み合わせ
-
高校数学です。 △ABCにおいて、...
-
数学の証明問題
-
ヤングの実験で質問です。この...
-
下の図において、直線ABな円O、...
-
数学Aの外分がわかりません。 ...
-
外心と内心、もしくは重心と外...
-
3次元空間上の2点を結ぶ線分の...
-
正四面体の問題
-
三点の座標から中心点の求め方
-
△OABに対し、OPベクトル=sOAベクトル+...
-
二等辺三角形の性質(定理)の...
おすすめ情報