|
| 図1 道路網の最短経路 |
「図1のような道路網のスタートからゴールまでの最短経路は何通りあるか？」
このような問題はどのように解けばよいでしょうか？
|
| 図2 道路網の補完 |
まずは碁盤の目のようになるように図2のように線を書き足します。
補完された交差点を交差点A、道路をB地点とします。すると、問題文を「AとBどちらも通らない」場合の最短経路は何通りか？というように解釈することができます。
補完された交差点を交差点A、道路をB地点とします。すると、問題文を「AとBどちらも通らない」場合の最短経路は何通りか？というように解釈することができます。
ここで、「AとBどちらも通らない」という条件の否定について考えます。
「AとBどちらも通らない」すなわち「Aを通らずかつBを通らない」の否定は「Aを通るまたはBを通る」です。これをベン図で表すと以下の図3のようになります。
「Aを通る」は左の楕円部分、「Bを通る」は右の楕円部分です。2つの楕円が重なった緑の部分は「A、B両方を通る」となります。
そして「Aを通る、またはBを通る」は赤と緑、青をあわせたものになります。
「AとBどちらも通らない」すなわち「Aを通らずかつBを通らない」の否定は「Aを通るまたはBを通る」です。これをベン図で表すと以下の図3のようになります。
|
| 図3 「Aを通るまたはBを通る」のベン図 |
そして「Aを通る、またはBを通る」は赤と緑、青をあわせたものになります。
このことから「Aを通るまたはBを通る（赤、緑、青）」を求めるには、
「Aを通る（赤、緑）」+「Bを通る（青、緑）」-「A、B両方を通る（緑）」
を考えれば良いということになります。
また、「AもBも通らない」場合の最短経路の数を求めるには、「補完した状態のすべて」の最短経路の数から「Aを通る、またはBを通る」場合の最短経路の数を引くことで求めることができます。
以上から、「補完した状態のすべて」の場合、「Aを通る」場合、「Bを通る」場合、「A、B両方を通る」場合それぞれの最短経路が何通りあるのかを計算します。
補完した状態のすべての最短経路
補完した状態の道路網は縦5マス×横7マスなので、
\[\frac{12!}{5! 7!}=792(通り)\]
となります。
「Aを通る」場合
|
| 図4 「Aを通る」場合 |
赤い部分は
\[\frac{3!}{1! 2!}=3(通り)\]
紫の部分は
\[\frac{9!}{4! 5!}=126(通り)\]
したがって、
\[3× 126=378(通り)\]
「Bを通る」場合
|
| 図5 「Bを通る」場合 |
紫の部分は
\[\frac{8!}{3! 5!}=56(通り)\]
青の部分は
\[\frac{3!}{1! 2!}=3(通り)\]
したがって、
\[56× 3=168(通り)\]
「A、B両方を通る」場合
|
| 図6 「A、B両方を通る」場合 |
赤の部分は
\[\frac{3!}{1! 2!}=3(通り)\]
緑の部分は
\[\frac{5!}{2! 3!}=10(通り)\]
青の部分は
\[\frac{3!}{1! 2!}=3(通り)\]
したがって、
\[3× 10× 3=90(通り)\]
よって、「Aを通る、またはBを通る」場合の最短経路の数は
\[378+168-90=456(通り)\]
であるから、求めたい「AとBどちらも通らない」場合の最短経路の数は
\[792-456=\textbf{336}(通り)\]
となります。
Share:
