右の図において, 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) なぜ、 解説にあるような場合分けになるのですか?