-
-
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 (通り)
ゆえに, 求める道順は