高校数学C 三段階の経路数—行列の積と列挙を比べて移動回数を区別する｜武蔵野個別指導塾

3本の辺を通る移動列を列挙し、行列の三乗と照らして移動回数と中継点2個の対応を確かめます。

よくあるのは、理系の高3が隣接行列の三乗を見て、中継点が3つあると読む場面です。出発点と到着点の間に中継点を3つ置けば、通る辺は4本になります。式の指数と頂点の個数を直接結び付けず、まず移動の区切りを紙に書き出しましょう。3回移動した列には、両端を含めて4つの頂点が並びます。

何を数える問題か

出方の1つは、接続図から指定された2点の間をちょうど3回移動する列を数える問題です。別の出方では隣接行列が与えられ、三乗の指定成分を求め、その値を列挙で説明します。さらに、同じ出発点と到着点で2回の移動と3回の移動を比較する問題もあります。移動回数が異なれば、同じ2点の間でも数は一致するとは限りません。

以下の「移動列」は、指定の辺を1回につき1本通った順に頂点を並べたものです。同じ頂点や同じ辺に戻ってもかまいません。したがって、頂点を繰り返さない単純な道や、辺の本数が最小の道を数える問題とは条件が異なります。辺に長さや時間の重みは付けず、移動回数を数えます。図の線が交差しても、頂点として名前を付けていなければ、そこで乗り換えられません。

3本の辺と2つの中継点

頂点は場所、辺は1回で移動できる接続を表します。無向辺は両方向に通れ、有向辺は矢印の向きに限って通れます。無向辺の重複と、同じ出発点から同じ到着点への有向辺の重複を除きます。また、自分自身に戻るループは設けません。頂点の並びを決め、隣接行列の行を出発、列を到着とします。対応する向きの辺があれば1、なければ0です。行と列は同じ順に並べます。

図1のように、出発から1回目の到着、2回目の到着、最後の到着までに辺が3本あります。途中に現れる2か所が中継点です。同じ文字が再び現れても、前後の移動が許されていれば別の時点として記録します。たとえば P から Q を経て P に戻り R へ進む場合、P は出発点でも2つ目の中継点でもあります。

隣接行列を A とすると、A の i 行 j 列は i から j への1回の移動の可否です。A² の i 行 k 列は、最初の中継点を候補ごとに固定して、2回で i から k へ進む列を数えます。その値に k から j への辺の有無を掛け、k について足したものが A³ の i 行 j 列です。前半の2回と最後の1回をつなぐので、合計は3回です。

この積和が列挙と対応する理由を確認します。3回の移動列は2回目の到着点 k をただ1つ持ちます。k を固定すると、i から k までの2回の移動列のそれぞれに、k から j への辺があれば最後の1回を付けられ、なければ付けられません。異なる k の組は重ならず、候補を足せば数え残しもありません。これは特定の数字に依存しない説明です。

基本例題：三角形の中を3回移動する

3地点 A、B、C の間に AB、BC、CA の無向辺があります。架空の構内の通路とし、各辺を往復できます。A から B へちょうど3回移動する列を、反復を許してすべて挙げ、個数を整数で求めましょう。A、B、C の順に並べた隣接行列の三乗でも確かめます。

図2のように各地点は他の2地点とつながっています。ループはないので、その場にとどまる移動はありません。移動列の順序まで記録し、同じ場所に戻る列も除かずに数えます。

まず、最後の1回で B に入る直前の地点は A または C です。直前が A なら、A から2回で A に戻る列は A-B-A と A-C-A の2通りです。直前が C なら、A から2回で C に着く列は A-B-C の1通りです。よって3回の列は次の3本です。

A-B-A-B
A-C-A-B
A-B-C-B

A から出発する各列の隣り合う2文字がいずれも辺でつながり、最後は B です。A-C-B-B は最後にループを必要とするため含めません。直前の地点を A と C に分けたので、ほかの候補はありません。

行列の行と列の順序は A、B、C で固定します。行列は3行3列なので、積の内側の次元は3でそろい、二乗も三乗も3行3列です。成分の単位は移動列の個数です。

A =  0 1 1
     1 0 1
     1 1 0

A² = 2 1 1
     1 2 1
     1 1 2

A³ = 2 3 3
     3 2 3
     3 3 2

求めるのは A³ の A 行 B 列です。積和の各項を移動列へ戻します。

2・1 + 1・0 + 1・1
= 2 + 0 + 1
= 3

最初の2は A への2回の戻り方、最後の1は C への2回の行き方に対応します。真ん中は B から B への辺がないため0です。行列で得た3と、実際の通路をたどって挙げた3列が一致します。最短の道を数えるなら直接の辺 AB が1本で済みますが、それは今回の3回という指定とは別の問いです。

標準例題：向きのある接続を数える

地点 P、Q、R の片道の接続が P→Q、P→R、Q→P、Q→R、R→P とします。矢印は移動できる向きを示し、他の接続はありません。P から R にちょうど3回で着く移動列を反復を許してすべて挙げ、個数を整数で求めましょう。

順序を P、Q、R とすると、行が出発、列が到着です。たとえば R 行 Q 列は0であり、P 行 R 列の1を逆向きに読んではいけません。3行3列どうしの積を計算します。

B =  0 1 1
     1 0 1
     1 0 0

B² = 2 0 1
     1 1 1
     0 1 1

B³ = 1 2 2
     2 1 2
     2 0 1

P 行 R 列を積和に戻すと次のとおりです。

2・1 + 0・1 + 1・0
= 2 + 0 + 0
= 2

最後に R へ入る直前は P または Q です。P から2回で P に戻る列は P-Q-P と P-R-P で、Q に2回で着く列はありません。したがって答えは P-Q-P-R、P-R-P-R の2通りです。どちらも各矢印を順方向に通り、3本の辺を使っています。2列目では P と R を再訪するので、反復を認める条件が結果に効いています。

発展例題：同じ端点でも回数で分ける

地点 U、V、W、X があり、無向辺は UV、VW、WX の3本です。ほかに辺はありません。U から X への2回と3回の移動列をそれぞれ反復を許してすべて挙げ、各個数を整数で求めましょう。3回の結果は行列の積でも確認します。

U からの1回目は V です。2回目は U または W なので、2回で X には着きません。3回目は、2回目が U なら V、W なら V または X に着きます。よって X に着く列は U-V-W-X の1通りです。反復を許していても、3回で到着する条件を満たす列はこの1通りになります。

U、V、W、X の順に行と列を置きます。4行4列の積なので、内側の次元は4でそろいます。必要な U 行を順に計算します。

C =  0 1 0 0
     1 0 1 0
     0 1 0 1
     0 0 1 0

C² の U 行 = 1 0 1 0
C³ の U 行 = 0 2 0 1

最後の成分は次の積和です。

1・0 + 0・0 + 1・1 + 0・0
= 0 + 0 + 1 + 0
= 1

2回目に W にいる1通りへ WX を付けた値です。2回の答え0と3回の答え1は、同じ端点でも移動回数が違うため別々に読み取ります。この接続では最短の本数も3ですが、一般に A³ が数えるのは3回の列であり、最短かどうかを自動で判定する値ではありません。

誤答を直す：頂点の数と辺の数

基本例題で「A から中継点を3つ置いて B へ進む」として A-B-C-A-B を数えたとします。図3のように、この列は頂点が5個、間の辺が4本です。各辺が存在することと、求める移動回数に合うことは別々の条件です。

原因は、三乗の3を中継点の個数と解釈したことです。頂点を1つ追加するたびに、直前の頂点との間に辺が1本増えます。修正するときは、出発点の後に矢印を3本書き、その先の空欄を3つ埋めます。最後の空欄を B と決めれば、自由に選ぶ中継点は2つです。

別の誤りは、3本の辺を確認せず A-B-B-B を挙げることです。これは移動回数の枠は合いますが、BB が辺でないため失敗します。反対に A-B-A-B を、出発点に戻ったという理由で除くのも誤りです。今回の条件は反復を許すため、3本の辺がすべて存在すれば数えます。まず回数、次に各辺の有無と向き、最後に反復条件を照合すると、異なる種類の誤りを区別できます。

行列でも誤りは起こります。A² の A 行 B 列を3回の答えとする場合は、2回分までしか掛けていません。また、有向辺の行列で B 行 A 列を読むと、逆向きの移動を数えます。式の横に出発と到着の文字、指数の横に移動回数を書くと、数字だけを追うときより検査しやすくなります。

練習問題

各問でループや明記されていない辺はなく、移動列では頂点や辺の反復を許します。答えは列をすべて挙げ、個数を整数で示してください。行列は指定順に行を出発、列を到着として作ります。

1. 地点 D、E、F に無向辺 DE、EF があります。D から E へちょうど3回の移動列を求めてください。
2. 地点 G、H、I に無向辺 GH、HI、IG があります。G から G へちょうど3回の移動列を求めてください。
3. 地点 J、K、L に有向辺 J→K、K→L、L→J があります。J から J へちょうど3回の移動列を求めてください。
4. 地点 M、N、O に有向辺 M→N、N→M、N→O があります。M から O への2回と3回の移動列をそれぞれ求めてください。
5. 地点 S、T、V、Y に無向辺 ST、SV、TY、VY があります。S から Y へちょうど3回の移動列を求めてください。

練習の解答と解き方

1

D の隣は E だけです。2回目は D または F へ進み、どちらからも3回目に E へ戻れます。列は D-E-D-E、D-E-F-E の2通りです。各列の3本はいずれも指定された辺です。

2回目が D の場合 1通り
2回目が F の場合 1通り
1 + 1 = 2

2

G の1回目は H または I です。3回目に G へ戻るには、2回目はもう一方の頂点になります。列は G-H-I-G、G-I-H-G の2通りです。直前が H または I のいずれかで尽くされ、それぞれの辺も実在します。

G-H-I-G が 1通り
G-I-H-G が 1通り
1 + 1 = 2

3

各地点から出る矢印は1本です。J から順にたどると J-K-L-J の1通りです。最後の L→J も指定された向きなので、3回で出発点に戻ります。逆向きの J-L-K-J は最初の矢印がないため数えません。

J → K → L → J
1・1・1 = 1

4

最初の移動は M→N です。2回で O に着く列は M-N-O の1通りです。3回では2回目に M または O に着きますが、M から O への辺も、O から出る辺もありません。したがって3回の列はなく0通りです。

2回: M-N-O の 1通り
3回: M-N-M から O へは進めない
3回: M-N-O からさらに進めない

O に2回で着いた後、その場で1回を消費することはできません。ループがない条件に戻して0を確認します。

5

1回目は T または V、2回目はどちらからも S または Y です。3回目に S または Y から進めるのは T または V なので、Y に着く列はなく0通りです。2回で Y に着く列があっても、3回の列として数えることはできません。

1回目: T または V
2回目: S または Y
3回目: T または V

各段階の候補を元の4本の辺と照合すると、3回目に Y が現れないことを確かめられます。0は計算の失敗ではなく、条件を満たす列が存在しないという答えです。

覚えておくこと

• 3回の移動は辺3本、両端を含む頂点4個、中継点2個です。
• 行を出発、列を到着とし、三乗の該当成分を読みます。
• 三乗は反復を許す3回の移動列を数えます。
• 列挙した各列の辺、向き、回数を確かめます。

つまずきの見分け方

個別指導で確かめたい記録は、完成した答えの数字だけではありません。頂点列に引いた区切り線、行列の行と列の見出し、積和の各項に添えた中継点を見ます。頂点が5個並んでいれば回数の読み違い、3本のうち逆向きの矢印があれば接続の読み違いと判断できます。列挙は合うのに成分が違えば、行と列の順序や二乗から三乗への掛け算を再確認します。

反復を許すかどうかを問題文に印を付けてから、戻る列を1つ実際にたどることも有効です。0通りの問題では空欄で終えず、最後の1回の出発候補と辺の有無を書き残します。移動の記録を辺ごとに確かめれば、三乗の値にどの列が含まれるかを説明できます。