-
-
378
基本例
例題 30 最短経路の数
右の図のように,道路が碁盤の目のようになった街がある。
地点Aから地点Bまでの長さが最短の道を行くとき,次
の場合は何通りの道順があるか。
(1) 全部の道順
(2) 地点 Cを通る。
[類 東北大〕
○
(3)地点Pは通らない。 (4) 地点Pも地点 Q も通らない。
+
基本27
AL
指針AからBへの最短経路は,右の図で 右進 または 上進する
ことによって得られる。 右へ1区画進むことを,上へ1区
画進むことを↑ で表すとき,例えば, 右の図のような2つの
まちがしが敗因
(3)
通行止め
からのリスタート最短経路は
地点配置
赤の経路なら
青の経路なら
-1--111-1-1
0000
111→11→1→→
で表される。 したがって, AからBへの最短経路は,
5個 16個の同じものを含む順列で与えられる。
(2) A → C, C→B と分けて考える。 積の法則を利用。
(3) (Pを通らない)=(全道順) (P を通る) で計算。
C
A
(4) すべての道順の集合をUPを通る道順の集合をP, Q を通る道順の集合をQと
n(PnQ)=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) 最短の道順は5個, 16個の順列で表されるから
11!
5!6!
11-10-9-8-7
5・4・3・2・1
462(通り)
(2) A から Cまでの道順 CからBまでの道順はそれぞれ
組合せで考えてもよい。
次ページの別解参照。
AからCまでで
3!
8!
-=3(通り), -=70(通り)
1!2!
4!4!
→1個, 2個
CからBまでで
よって, 求める道順は
3×70=210(通り)
→4個 14個
5!
5!
(3)Pを通る道順は
× -=10×10=100 (通り)
2!3!
2!3!
よって, 求める道順は
7!
3!
(4) Q を通る道順は
×
3!4!
1!2!
462-100=362 (通り)
=35×3=105 (通り)
(Pを通らない)
=(全体)(Pを通る)
PとQの両方を通る道順は
5!
3!
=10×3=30(通り)
2!3! 1!2!
▼PからQに至る最短の
道順は1通りである。
よって, Pまたは Q を通る道順は
ゆえに, 求める道順は
100+105-30=175 (通り)
462-175=287 (通り)