O000
基本 例題31 最短経路の数
右の図のように,道路が碁盤の目のようになった街がある。
地点Aから地点Bまでの長さが最短の道を行くとき, 次
の場合は何通りの道順があるか。
(1) 全部の道順
(3) 地点Pは通らない。(4)地点Pも地点Qも通らない。
342
【類東北大)
(2) 地点Cを通る。
ケ生こる
C
A。
基本 28
(3
によって得られる。右へ1区画進むことを→, 上へ1区画進むこ
とを1で表すとき,例えば, 右の図のような2つの最短経路は
黒の経路なら ↑↑↑→→↑↑→→→→
赤の経路なら →→→→→→→→→↑
で表される。よって, AからBへの最短経路は, →5個, ↑6個
の同じものを含む順列で与えられる。
(2) A→C, C→Bと分けて考える。積の法則 を利用。
(3) (Pを通らない)= (全道順)- (P を通る)で計算。
(4)すべての道順の集合をび, Pを通る道順の集合をP, Qを通る道順の集合をQとする
指針> AからBへの最短経路は,右の図で 右進 または 上進 すること
P
C
A
n(PnQ)=n(PUQ)=n(U)-n(PUQ)
(PもQも通らない)3 (全道順)- (PまたはQを通る)
n(PUQ)=n(P)+n(Q)-n(PnQ)
と,求めるのは
イド·モルガンの法則
つまり
個数定理
ここで
8つまり
(PまたはQを通る)=(P を通る)+(Qを通る)- (P とQを通る)…
のは( e
解答
右へ1区画進むことを→, 上へ1区画進むことを1で表す。
(1) 最短の道順は→5個, 16個の順列で表されるから
さへ並
は左健
(組合せで考えてもよい
次ページの国調編
11·10-9-8-7
=462(通り)
ISIS
三
5!6!
5.4-3-2-1
(2) AからCまでの道順, Cから Bまでの道順はそれぞれ
『AからCまでで
→1個, ↑2個
CからBまでで
4個, 14個
3!
8!
-=3(通り),
-=70 (通り) 当合味!
1!2!
4!4!
よって,求める道順は
3×70=210(通り)
(3) Pを通る道順は
5!
2!3!
よって,求める道順は
5! S
=10×10=100(通り)
2!3!
(Pを通らない)
「弁体)-(Pを選る
462-100=362 (通り)
(4) Qを通る道順は
7!
3!
