学年

教科

質問の種類

英語 高校生

最短経路の問題です! こう言う問題が出たときどちらのほうが楽に解けると思いますか? 今までの自分は写真の一枚目のやり方で解いていました。今後どちらの方法でこう言う問題を解けばいいのでしょうか? 写真が見づらくてすみません!

342 台の図のように,道路が基盤の目のようになった街がある。 地点Aから地点Bまでの長さが最短の道を行くとき, 次 の場合は何通りの道順があるか。 (1)全部の道順 基本 例題31 最短経路の数 『類東北大) (2) 地点Cを通る。 3) 地点Pは通らない。(4) 地点Pも地点Qも通らない。 によって得られる。右へ1区画進むことを→,上へ1区面進むこ とを「で表すとき,例えば、右の反のような2つの最短経路は 黒の経路なら 11→→i1→→→ 赤の経路なら - t1→ー で表される。よって、AからBへの最短経路は, →5個、16個 の同じものを含む順列 で与えられる。 (2) A→C, C→Bと分けて考える。 積の法則 を利用。 (3)(Pを通らない)=(全道順)-(Pを通る)で計算。 (4) すべての道順の集合をし, Pを通る道順の集合をP. Qを遠る道頓の集台を0ょ、 と,求めるのは 指計> AからBへの最短経路は、右の図で 右進 または 上進 すること イド-モルガンの注意 n(Pnの)=n(PUQ)=n(U)-n(PUQ) つまり (PもQも通らない=(全道順)-(PまたはQを通る) (個数定理 ここで n(PUQ)=n(P)+n(Q)-n(PnQ) つまり (PまたはQを通る)=(Pを通る)+(Qを通る)-(P とQを通る) 解答 右へ1区画進むことを一,上へ1区画進むことを1で表す。 (1)最短の道順は→5個,↑6個の順列で表されるから く組合せで考えてもよい。 次ページの国参照。 11·10-9-8-7 -=462(通り) 5!6! 5.4-3-2-1 (2) AからCまでの道順, CからBまでの道順はそれぞれ 4AからCまでで →1個、12個 CからBまでで →4個、14個 3! =3 (通り), 1!2! 8! -=70 (通り) 4!4! よって,求める道順は 3×70=210(通り) (3) Pを通る道順は 5! 5! 2!3! =10×10=100 (通り) 2!3! よって,求める道順は 462-100=362 (通り) 3! 121 -35×3=105(通り) 4(Pを通らない) =(全体)-(Pを通る) (4)Qを通る道順は 7! 3!4! PとQの両方を通る道順は 5! 3! =10×3=30(通り) PからQに至る最短の 道順は1通りである。 2!3! 1!2! よって, PまたはQを通る道順は 100+105-30=175 (通り) 462-175=287 (通り) ゆえに, 求める道順は

解決済み 回答数: 1