数学IA 最短経路の順列

数学IA　最短経路の順列

数学IAの問題です。

図のような市街路を、遠回りしないでAからBまで行く順路について、次の順路の総数を求めよ。
(1)AからBまで行く道の順路の総数を求めよ
(2)Cを通って、AからBまで行く順路
(3)Cを通らずに、AからBまで行く順路
という問題です。

でも最初の(1)の問題の求め方が分からなくて困っています。
どなたか教えてください。

回答よろしくお願いします。

No.3 回答者： naniwacchi 回答日時： 2010/10/25 13:11

こんにちわ。

#1(#2)さんが丁寧に説明されているので、おおざっぱな「見方」だけ。

＞(2)Cを通って、AからBまで行く順路
必ず点Cを通らなければならないので、A→C、C→Bと分けて考えますね。
そして、
・A→Cは、線分ACを対角線とする長方形
・C→Bは、線分BCを対角線とする長方形

だけに注目するようにします。
図でいえば、左上や右下の部分は最短経路をとるためには通れないということです。
こうすれば、少しはすっきりと見えると思います。


(1)は一度「空白」の中に線と点Dを描き入れて考えてみればいいです。

No.2 回答者： nag0720 回答日時： 2010/10/25 05:50

＞前者は分かりますが、後者が分かりません。

（Dを通ってAからBまで行く順路の総数）＝（AからDまで行く順路の総数）×（DからBまで行く順路の総数）

No.1 ベストアンサー 回答者： nag0720 回答日時： 2010/10/25 02:01

図の中に道がないところがありますが、もし縦横すべての道があったとしたらAからBまで行く順路の総数は分かりますか？

道がないところの中央をDとして、縦横すべての道があった場合に、Dを通ってAからBまで行く順路の総数は分かりますか？

(1)の数は、上記の前者の数から後者の数を引いたものになります。

この回答への補足

回答ありがとうございます。

前者は分かりますが、後者が分かりません。

補足日時：2010/10/25 02:22