右の図において, P地点からQ 地点に達する最短経路
について考えよう。
(1) P地点から, A地点を通り, Q 地点に達する最短
B.
A
経路はアイウ 通りある。
(2)P地点から, B地点を通り, Q 地点に達する最短
経路はエオ通りある。
P
(3) P地点からQ 地点に達する最短経路は全部で カキク 通りある。
(解説)
右下の図のように, 点 B', B", C, D, E を定める。
5!
(1) P地点からA地点に達する最短経路は
=5 (通り) E
4!1!
6!
C B
B
A地点からQ 地点に達する最短経路は
=20 (通り)
3!3!
B
A
よって, P地点から, A地点を通り, Q地点に達する最短
経路は 5×20=100 (通り)
P
D
(2) P地点からB' 地点に達する最短経路は
4!
3!1!
=4 (通り)
B'地点からB地点, B地点からB" 地点に達する最短経路はそれぞれ
5!
B地点から Q 地点に達する最短経路は
-=10(通り)
3!2!
よって, P地点から, B地点を通り, Q 地点に達する最短経路は
4x1x1x10=40 (通り)
(3) P地点から, C地点を通り, Q 地点に達する最短経路は
4!
7!
× =28(通り)
1!3! 6!1!
通り
6!
P地点から, D地点を通り, Q 地点に達する最短経路は
=15(通り)
P地点から, E地点を通り, Q地点に達する最短経路は
ゆえに, P地点からQ 地点に達する最短経路は全部で
100 +40 +28 +15+1=184 (通り)
2!4!
通り
0
0
(2) なぜ、 (5/3 ! x2 !)x6 ! /4! x2 ! ではないのですか?
(3) なぜ、 解説にあるような場合分けになるのですか?