武蔵野個別指導塾の特徴
高校数学C 条件付きの経路数—使える辺と移動回数を限定して数え方を組み直す｜武蔵野個別指導塾
通行止め後に隣接行列を作り直し、2回・3回の移動列を数えて、再訪を禁じた場合も調べます。
よくあるのは、理系の高3が通行止めの辺を図から消したのに、変更前の隣接行列の累乗をそのまま答えに使う場面です。計算が正しくても、数えている移動には通れない区間が混ざっています。どの辺を使えるか、何回移動するか、同じ地点を再訪してよいかを先に決めると、数字が何を数えたか追跡できます。
条件が変わると、数える対象も変わる
出方の1つは、双方向に通れた区間が通行止めになった後、指定された回数で目的地に着く移動列を数える問題です。通行止めの前後で図と表をそれぞれ作り、同じ成分を比較します。通れない辺を含む列が何本消えたかまで確認すると、差の意味がはっきりします。
別の出方は、ちょうど2回とちょうど3回の移動を比べる問題です。2回以内ではなく、辺を指定回数だけ通ります。途中で目的地に着いてから出発し直す列も、反復が許されるなら条件に合います。始点と終点が同じ往復も、指定された移動回数を満たせば数えます。
もう1つは、同じ地点を2度通れないという制限です。通常の隣接行列の累乗は、通った地点の履歴を成分に記録しません。そのままでは再訪を取り除けないので、小さい図では候補を列挙して条件を調べます。以下の経路数は、特に断らない限り、頂点や辺の反復を許す指定回数の移動列の数です。距離や最短所要時間は数えません。
辺を消す操作と表の意味
地点を頂点、直接移動できる区間を辺で表します。ここでは各辺は双方向に通れ、同じ2地点を結ぶ辺は1本、同じ地点から同じ地点に直接戻る辺はないものとします。線の交差は、頂点として示した場合に限り地点です。辺に距離や時間の重みは付けません。
頂点の並びを決め、行を出発、列を到着とします。直接移動できれば成分を1、できなければ0とした表が隣接行列です。双方向の辺を閉じると、両方向の成分を0に直します。片方向だけが閉じる場面なら、閉じた向きの成分だけを直す必要があります。通行止めという言葉だけで両方を消さず、問題の条件を見ます。
図1のように、PとQの間を双方向に閉じると、PからQとQからPの両方が0になります。表の残りの成分は変えません。図の中の線を1本消す操作が、表では対称な2か所の変更に対応します。
変更後の行列をBとすると、B²の出発P・到着Rの成分は、中継点を順に選び、Pから中継点へ行ける数と中継点からRへ行ける数を掛けて足したものです。各項はその中継点を持つ2回の移動列を数えます。中継点が異なれば列も異なるので、足し合わせても重複しません。B³では先に2回移動した後の地点を経て、もう1回移動します。3回の移動には中間の位置が2つあります。
累乗に使う表は、その移動のたびに同じ通行条件が適用される場合のものです。途中で閉鎖状況が変わる場合は、各段階の表を順番に掛けます。回数の指定、向き、再訪の可否は、それぞれ別の条件として読み取ります。
基本例題：閉じた区間を表から消す
地点A、B、Cを結ぶ双方向の辺がAB、AC、BCの3本あります。BCが双方向に通行止めです。辺や頂点の反復を許し、AからCまでちょうど2回、またちょうど3回移動する列をそれぞれ個数で求めてください。辺は閉鎖後ずっと同じ条件です。
図2のように、閉鎖後はABとACが残ります。行と列をともにA、B、Cの順に固定し、行を出発、列を到着とすると、変更前の行列をM、変更後をBとして次のように表せます。
M = [ 0 1 1 ] B = [ 0 1 1 ]
[ 1 0 1 ] [ 1 0 0 ]
[ 1 1 0 ] [ 1 0 0 ]Bの2行3列と3行2列が閉鎖によって0になりました。B²のA行C列は、A、B、Cの順に中継点を選んで計算します。
(B²)AC = 0・1 + 1・0 + 1・0
= 0Aから1回で行けるのはBかCですが、BからCは閉鎖中で、CからCへ直接移動する辺もありません。したがって2回の列は0個です。ここで得た0は、閉鎖後の辺だけを使ってAからCへ2回で着く方法がないことを表しており、計算を誤ったわけではありません。
3回の場合は、まず2回の移動先を調べます。
B² = [ 2 0 0 ]
[ 0 1 1 ]
[ 0 1 1 ]
(B³)AC = 2・1 + 0・0 + 0・0
= 2Aに2回で戻る方法はA→B→AとA→C→Aです。そこからACを通るので、3回の列はA→B→A→C、A→C→A→Cの2個です。後者はACを繰り返しますが、この問題では反復が許されます。各列の矢印が残った辺を表し、矢印が3本あることも確認できます。
閉鎖前は2回でA→B→Cの1個がありました。3回ではA→B→A→C、A→C→A→C、A→C→B→Cの3個があります。閉鎖後の差はそれぞれ1個です。消えた列はいずれもBCを含むため、表の修正と列挙が対応します。
標準例題：移動回数と再訪を分ける
地点D、E、F、Gの間に双方向の辺DE、DF、EF、EG、FGがあります。EFを双方向に閉じた後、DからGへちょうど2回とちょうど3回で移動する列をそれぞれ個数で求めてください。頂点と辺の反復を許します。
残る辺はDE、DF、EG、FGです。行と列をD、E、F、Gの順にして、変更後の行列をCとします。
C = [ 0 1 1 0 ]
[ 1 0 0 1 ]
[ 1 0 0 1 ]
[ 0 1 1 0 ]2回でGへ着くには、最後の出発点がEかFです。それぞれDから直接行けるため、積和は次のようになります。
(C²)DG = 0・0 + 1・1 + 1・1 + 0・0
= 2列はD→E→G、D→F→Gの2個です。次にDから2回の移動後にどこにいるかを計算します。
C²のD行 = [ 2 0 0 2 ]
(C³)DG = 2・0 + 0・1 + 0・1 + 2・0
= 02回後はDかGにしかいません。いずれにもGへの直接の辺がないので、3回では着けません。実際、2回後の列はD→E→D、D→F→D、D→E→G、D→F→Gで、そこから1回進んでも終点はEかFです。2回で着けるから3回でも着けるとは限りません。移動せず待つ操作は辺として与えられていないため、回数合わせに使えません。
閉鎖前ならD→E→F→GとD→F→E→Gの2個が3回の列に加わります。閉鎖したEFを使うため、どちらも閉鎖後は不可です。閉鎖前後の差を見れば、削除した辺を経由する列が取り除かれたことも点検できます。
発展例題：段階ごとに通れる辺が変わる
地点H、J、Kの間に双方向の辺HJ、HK、JKがあります。1回目は3本とも通れますが、2回目以降はJKが双方向に閉鎖されます。HからKへちょうど3回移動する列を個数で求め、さらに頂点の再訪を禁止した場合の個数も求めてください。最初の場合は反復を許します。
行と列の順をH、J、Kに固定します。1回目の行列をP、2回目以降の行列をQとすると、求める成分はPQQのH行K列です。Q³では1回目も閉鎖したことになり、条件と合いません。
P = [ 0 1 1 ] Q = [ 0 1 1 ]
[ 1 0 1 ] [ 1 0 0 ]
[ 1 1 0 ] [ 1 0 0 ]
PのH行とQの積 = [ 2 0 0 ]
(PQ²)HK = 2・1 + 0・0 + 0・0
= 21回目にHからJまたはKへ進むと、閉鎖後の2回目はHに戻るほかありません。3回目にHからKへ進むため、H→J→H→KとH→K→H→Kの2個です。1回目に使えるJKは、始点Hからは直接使わないので、この問いの答えには影響しません。それでも段階ごとの条件を表にすることは、別の始点にも正しく対応するために必要です。
頂点の再訪を禁じると、上の2列はいずれもHを再訪するので0個です。3回の移動では始点と終点を含めて4つの位置が現れますが、頂点は3個しかありません。したがってどの列でも再訪を避けられず、0個という結論を別の見方でも確かめられます。累乗の値2から無条件に1を引くような処理では、禁止される列の本数を正しく判断できません。
元の表を使った誤答を直す
基本例題で、閉鎖前のM²のA行C列を計算し、1個と答える誤りを考えます。積和自体は次のとおりです。
(M²)AC = 0・1 + 1・1 + 1・0
= 1この1は中継点Bに対応します。しかしA→B→Cの後半は、閉鎖されたBCです。図3のように、答えの1個を具体的な移動列に戻すと、元の条件との食い違いが見えます。
原因は、計算式の足し算ではなく、計算に入れた表が閉鎖前の状態を表していることです。BCを双方向に閉じたら、B行C列とC行B列を0にしてから積を作り直します。その結果は0個で、通れる2回の列が存在しないことと一致します。
片方向の閉鎖なのに両方を消す誤りもあります。その場合は矢印ごとに出発と到着を読み、閉鎖されていない向きの成分を残します。また、3回の指定にB²を使うと、2回移動した結果を答えることになります。式の指数と列の矢印の本数を見比べてください。
反復禁止を見落とした場合はさらに注意が必要です。閉鎖後のB³が数えた2個はどちらもAを再訪します。もし基本例題に頂点の再訪禁止を追加すれば、正しい答えは0個です。辺だけの反復禁止なら、A→B→Aも同じ無向辺ABを2度使うので、やはりそれぞれの列を検査します。頂点の再訪禁止と辺の反復禁止は同じ条件ではなく、問題文に応じて判定します。
練習問題
各問題は独立した自作の設定です。辺は双方向で、特に指定しない限り頂点と辺の反復を許します。列の数を整数で答えてください。
- 地点L、M、Nの辺はLM、LN、MNです。MNを双方向に閉じた後、LからNへちょうど2回移動する列は何個ですか。
- 地点R、S、Tの辺はRS、RT、STです。STを双方向に閉じた後、RからTへちょうど3回移動する列は何個ですか。
- 地点U、V、W、Xの辺はUV、UW、VX、WXです。UからXへちょうど2回および3回移動する列は、それぞれ何個ですか。
- 地点P、Q、R、Sの辺はPQ、QR、RS、SP、PRです。PRを双方向に閉じた後、PからRへちょうど2回移動する列は何個ですか。さらに頂点の再訪を禁止した場合の個数も求めてください。
- 地点A、D、Eの辺はAD、AE、DEです。1回目は全辺を通れ、2回目はDEが双方向に閉じます。DからEへちょうど2回移動する列は何個ですか。
練習問題の解答と解き方
- 0個です。閉鎖後のLからの移動先はMかNです。MからNへの辺は閉じ、NからNへの辺もないので、2回目にNへ着く列はありません。行列のL行N列の積和も次のとおりです。
0・1 + 1・0 + 1・0 = 0- 2個です。閉鎖後の2回の移動列でRに戻るのはR→S→RとR→T→Rです。その後にRTを通るため、R→S→R→T、R→T→R→Tとなります。2回後にSやTに着く列はないので、ほかに候補はありません。
2・1 + 0・0 + 0・0 = 2- 2回は2個、3回は0個です。2回の列はU→V→X、U→W→Xです。2回後の行列のU行は、U、V、W、Xの順に [2, 0, 0, 2] です。UとXからXへの直接の辺はないため、3回目にXへ着けません。
2回: 1・1 + 1・1 = 2
3回: 2・0 + 0・1 + 0・1 + 2・0 = 0- どちらも2個です。閉鎖後は四角形の辺が残り、P→Q→RとP→S→Rがあります。各列で3地点は異なるため、頂点の再訪を禁じてもどちらも残ります。PRを使う列を残していないことも図の辺の一覧から確かめられます。
2回: 1・1 + 1・1 = 2
再訪なし: 2個とも条件を満たす- 1個です。1回目にDからAまたはEへ行けます。2回目はAからEへ進めますが、EからEへ進む辺はありません。したがってD→A→Eのみです。1回目の表をP、2回目の表をQとし、順をA、D、Eとすると、積の成分は次のようになります。
(PQ)DE = 1・1 + 0・0 + 1・0
= 12回とも閉鎖後の表を使ってもこの設定では同じ数になりますが、それは偶然です。表の選び方は、答えの数が一致するかではなく各回の通行条件で決めます。
覚えておくこと
- まず使える辺と向きを図と隣接行列に反映します。
- 行を出発、列を到着に固定し、移動回数に対応する積を作ります。
- 累乗は反復を許す移動列を数えます。
- 再訪禁止は列を取り出して条件を調べます。
- 答えの列を元の辺と回数に戻して確かめます。
つまずきの見分け方
計算結果だけでなく、閉鎖前後の図、頂点順を書いた行列、積和の各項に対応する中継点の記録を見ます。図で辺を消したのに表の成分が残っていれば、表への移し替えが原因です。表が正しくても指数が違えば、移動回数と中間の位置を混同している可能性があります。
個別指導では、まず生徒に1本の列を矢印で書いてもらい、各矢印が使える辺か、矢印が指定の本数かを一緒に確認します。次に列挙した候補が積和のどの項に入るかを尋ねます。再訪禁止の問題なら、同じ頂点や辺に印を付ける記録も確認します。条件を満たす列を具体的に示せれば、行列の数字に意味が戻ります。
読んで終わりにするか、ここから変えるか。
武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。
まず15分だけ電話で話したい方は、無料電話相談（15分）から。塾からお電話を差し上げます。
ほかの記事
本気になった日が、入塾の日。
お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。
電話は年中無休。365日、24時間、お電話可能。