気ままな数学ノート

「調べても分からない」に寄り添う

MENU

【最短経路】PもCも!も使わない万能な解き方を紹介します

◎問題

上の図において、次のような経路は何通りあるか答えなさい。

(1) AからBまでの最短経路

(2) AからBまでの最短経路でCを必ず通る経路

(3) AからBまでの最短経路でCを通らない経路

1) AからBまでの最短経路

手順1.端に1を書いていく

端の部分へ行く方法は1通りしかないので
数字の1を書いていきます

手順2.数を足していく

  へ行くためには,どちらかのを通らなかればならないので
  への行き方は 1+1=2 通り

手順3.足し算を繰り返す

書かれている数を足していけば
Bへ行く方法は35通りと求められます。

2) AからBまでの最短経路でCを必ず通る経路

手順1.必要な経路だけをかく

点Cを通る経路だけを残します

手順2.数字を書いて足していく

数字を書いて足していくと
AからCを通ってBまで行く方法は
18通りと求められますね

3) AからBまでの最短経路でCを通らない経路

手順1.必要な経路だけをかく

点Cの周りの経路を消します

手順2.数字を書いて足していく

数字を書いて足していくと,
Cを通らずにBまで行く方法は
17通りと求められますね

さいごに

この方法を知っていれば,複雑な経路の問題でも考えられるようになるので
知っておくと検算などで使えそうですね