なかけんの数学ノート

【応用】最短経路の数

ここでは、最短経路の数について見ていきます。【標準】最短経路の数での内容を少し応用した問題を考えます。また、困ったときに使える技も紹介します。

[広告]

通らない最短経路

例題
線の上を通って、AからBへ最短で移動する方法を考える。
expert-number-of-shortest-paths-01
(1) Cを通らない行き方は何通りあるか。
(2) Dを通らない行き方は何通りあるか。
(3) CもDも通らない行き方は何通りあるか。

「通らない」経路を直接考えるのは面倒です。Cを通らない経路は、スタートしてすぐに右に進む経路や、上に2回進む経路、上に3回進む経路があり、ケースが多いです。直接数えるよりも、全体から「通る」経路を除いたほうが考えやすいです。【標準】反対側を数える【基本】補集合の要素の個数で見た、補集合を使った考え方ですね。

Cを通る場合は、Cの左の交差点Cのすぐ右の交差点の2か所を両方とも通らなければなりません。他の道は自由です。Cの左の交差点への経路は1通りです。Cのすぐ右の交差点からBに行くには、5回の移動のうち、2回上に移動するので ${}_5 \mathrm{ C }_2$ 通りです。AからBまでは、7回の移動のうち3回上に移動すればいいので、(1)の答えは\[ {}_7 \mathrm{ C }_3 -1\times {}_5 \mathrm{ C }_2 = 35-10=25 \]通り、となります。

同じように、(2)も、Dを通る経路を考えましょう。AからDへは、5回の移動のうち2回上に行けばいいです。DからBへは、2回の移動のうち1回上に行けばいいですね。それぞれ独立に経路を選べるので、(2)の答えは\[ {}_7 \mathrm{ C }_3 -{}_5 \mathrm{ C }_2\times {}_2 \mathrm{ C }_1 = 35-20=15 \]通り、となります。

次に(3)ですが、これは少し注意が必要です。「CもDも通らない」経路以外というのは、「Cを通る、または、Dを通る」です。「かつ」ではないことに注意です(参考:【標準】補集合の要素の個数)。「または」なので、【基本】和集合の要素の個数で見たように、それぞれの個数の和から、共通部分を除外しないといけません。

共通部分というのは、「CもDも通る」経路ということです。Aを出発し、Cの左側の交差点を通り、Cのすぐ右側の交差点も通り、Dに移動してから、Bに移動する、という経路です。(1)や(2)と同様に考えると\[ 1\times {}_3 \mathrm{ C }_1 \times {}_2 \mathrm{ C }_1=6 \]通りとなります。(1)と(2)の計算途中から、「Cを通る」経路は10通り、「Dを通る」経路は20通り、先ほど求めた通り、「CもDも通る」行き方は6通りなので、「Cを通る、または、Dを通る」経路の数は\[ 10+20-6=24 \]通りとなります。よって、「CもDも通らない」行き方は\[ 35-24=11 \]通り、となります。

なお、「Cを通らない」ということは、図が次のようになっていることと同じです。
expert-number-of-shortest-paths-02
Cを通る道がない状態です。上の図に対してAからBへの最短経路の数を聞かれたときにも、今回の例題と同じように解きます。

では、「Dを通らない」というのは、道がどうなっているときでしょうか。次のように、Dを通るすべての道がない取り除いたときと同じです。
expert-number-of-shortest-paths-03
問題の設定が変わっても、同じように考えられるようになりましょう。

困ったときに使える技

さて、最短経路の個数を数える問題では、「〇回移動するうち、〇回上に移動する方法」を数える方法を使ってきました。しかし、上のように複雑な状況になってくると、本当に答えがあっているか不安になることもあると思います。そうしたときに使えるチェック方法があるので紹介しておきます。

【標準】最短経路の数#ゴール直前の状況についてでも書きましたが、ゴールは、左から来るか下から来るかしかありません。ただ、これはゴール時点だけでなく、すべての点で成り立ちます。

そのため、各点について、左の点への経路数と下の点への経路数を足すと、その点への経路数が出てくることになります。

ためしにやってみましょう。上の例題の(3)「CもDも通らない」行き方を考えます。3回目の移動までを書いた状態が、下の図です。
expert-number-of-shortest-paths-04

まず、点Aは1通りです。Aの右の点、Aの上の点も1通りです。Cの右の点は、Cを通らないため下から来るしかないから、1通りとなります。Aから右へ2、上へ1移動した点は、左からと下からの行き方があり、それぞれ1通りなので、この点への行き方は2通りとなります。

通らない道に注意して、左の点の数字と下の点の数字をどんどん足していくだけです。最後まで数字を書いていくと、次のようになります。

expert-number-of-shortest-paths-05
Dを通らないことに注意すると、上のようになります。Bへの経路数は、左の点の数字と下の点の数字を足して、11通りとなり、例題(3)の答えと一致します。道が大きくなると使えませんが、小さい場合には、このやり方で計算結果を確かめるために使えます。

おわりに

ここでは、最短経路の数を求める問題を考えました。今まで学んだことを組み合わせて解くので、不安な部分がある場合は、前に戻って復習しながら考えましょう。

また、困ったときに使える技も紹介しました。検算で使えるので、これも覚えておきましょう。

[広告]
対象者: 数学A
分野: 場合の数と確率
トピック: 場合の数
レベル: 応用
キーワード: 場合の数, 経路
更新日:2017/02/20