高校数学C 二段階の経路数—中継点ごとの場合を足して行列の二乗へつなぐ｜武蔵野個別指導塾

中継点ごとの積和と往復の列挙を照らし、対角成分に現れる二段階の経路数を読み解きます。

よくあるのは、理系の高3が地点のつながりを数表に直し、2回移動した後に出発点へ戻る場合を数え落とすという場面です。出発点と到着点が同じなら移動していない、と考えると、途中で別の地点を訪れた往復まで消えてしまいます。何回辺を通ったかと、最後にどこにいるかは別の条件です。

何を数える問題か

ここでいう経路は、辺をちょうど2回たどったときの、出発点・中継点・到着点の順に並べた移動列です。同じ頂点や同じ辺を再び使ってもよいものとします。したがって、出発点に戻る往復も数えます。頂点を重複して通らない道や、最短経路を数える問題とは条件が異なります。

典型的な出方は3つあります。図から指定した2地点の間の移動列を列挙する問い、隣接行列の二乗から指定成分を求める問い、対角成分の意味を往復として説明する問いです。いずれも、ちょうど2辺という条件を読み落とさないことが出発点です。0回の移動や1回の移動は、同じ地点に到着しても数えません。

以下の無向グラフでは、辺は両方向に通れます。頂点から自分自身への辺であるループと、同じ2頂点間の重複辺はありません。有向の場合は矢印の向きに従うという条件を加えます。図の線が途中で交差しても、そこに頂点を置いたと明示されていなければ乗り換えはできません。

中継点を固定して数える

頂点を A、B、C の順に並べ、行を出発点、列を到着点として隣接行列を作ります。辺があれば成分を1、なければ0とします。無向の辺では両方向が通れるため、対応する2つの成分は等しくなります。対角成分が0なのは、ここでループを置かないためです。

図1のように、A から C への2辺の移動は、中継点を B に固定すると A から B、B から C の両方が通れるかで決まります。中継点が別なら移動列も別なので、それぞれの場合の数を足せます。図1では B を経由する1通りが見えます。

図1の2本の辺は移動の順を示します。中継点を1つに定めた場合の数は、前半の選び方と後半の選び方の積です。今回の0・1の表では、どちらかが0なら積は0、両方が1なら積は1です。中継点の候補を順に調べ、その積を合計すると数え漏れや重複を防げます。

隣接行列を M とすると、M の二乗は M を同じ順序で2回掛けた行列です。その A 行 C 列の成分は、M の A 行と C 列の対応する成分の積和です。内側の分類はいずれも中継点 A、B、C の順です。出力の行は出発点、列は到着点で、成分の単位は移動列の通りです。行と列を逆に読むと、有向グラフでは特に別の数になります。

同じ図に対して、A 行 A 列も同様に計算します。これは移動しない方法の数ではなく、2辺を使って A に戻る方法の数です。ループがなくても、A と隣り合う B を通る A、B、A という往復はあります。隣接行列の対角が0だからといって、二乗の対角まで0とは限りません。

基本例題：三角形の地点を往復する

3地点 A、B、C の間に、辺 AB、BC、CA がそれぞれ1本あります。いずれも両方向に通れます。頂点や辺の反復を許して辺をちょうど2回通るとき、A から C への移動列と A から A への移動列をそれぞれ列挙し、通り数を整数で求めます。さらに隣接行列の二乗で両方を確かめます。

図2のように3地点は互いに辺で結ばれています。辺の長さは数え方に関係せず、接続と移動回数が条件です。

A から C へ行く中継点を調べます。A はループがなく、C もループがないので中継点にできません。B なら2本とも通れるため、移動列は A、B、C の1通りです。A に戻る場合は、B を経由する A、B、A と、C を経由する A、C、A の2通りです。いずれも辺を2回通っています。

行と列を A、B、C の順にした隣接行列と二乗は次のとおりです。

      A B C
M = [ 0 1 1 ]
    [ 1 0 1 ]
    [ 1 1 0 ]

M² = [ 2 1 1 ]
     [ 1 2 1 ]
     [ 1 1 2 ]

必要な成分を途中から計算すると、次のようになります。

A 行 C 列 = 0・1 + 1・1 + 1・0
            = 0 + 1 + 0
            = 1 通り
A 行 A 列 = 0・0 + 1・1 + 1・1
            = 0 + 1 + 1
            = 2 通り

A 行 C 列の3項は、それぞれ A、B、C を中継点とする場合です。A 行 A 列では最後の2項が2つの往復に対応します。図2の辺に各列を戻して、各移動が存在し、2回で終了することを確かめられます。表の計算が合っていても、元の図への写し間違いは別にあり得るため、この照合には意味があります。

標準例題：枝分かれした接続を調べる

4つの展示室 P、Q、R、S があり、両方向に通れる通路は PQ、PR、QR、RS の4本です。ループと重複通路はありません。通路をちょうど2回通り、部屋や通路の反復を許すとき、P から R、R から R の移動列をそれぞれ列挙し、通り数を整数で求めます。

P からの1回目の到着先は Q または R です。Q から R へ進めますが、R から R への通路はありません。したがって P、Q、R の1通りです。R から1回で行ける部屋は P、Q、S です。いずれからも R に戻れるので、R、P、R、R、Q、R、R、S、R の3通りです。ここでは読点で区切った3地点ずつが各移動列です。

P、Q、R、S の順の行列で、対応成分を確かめます。

M = [ 0 1 1 0 ]
    [ 1 0 1 0 ]
    [ 1 1 0 1 ]
    [ 0 0 1 0 ]

P 行 R 列 = 0・1 + 1・1 + 1・0 + 0・1
            = 1 通り
R 行 R 列 = 1・1 + 1・1 + 0・0 + 1・1
            = 3 通り

4項は中継点 P、Q、R、S に順に対応します。たとえば P 行 R 列の最後の項は、S から R へ通れても P から S へ直接行けないので0です。片方の辺だけを確認して数えないようにします。列挙した各列を通路の一覧に戻すと、実際に2本の通路を順に通れることも確認できます。

無向でループのない今回の条件では、ある頂点から出て2辺で戻る方法は、その頂点に接する辺の数に等しくなります。1回目に選んだ隣接頂点から同じ辺を戻る以外に、2回目で出発点に着く方法がないためです。ただしこれは反復を許す場合です。同じ辺の再使用を禁じるなら、この往復は認められません。

発展例題：矢印の向きと戻り方

地点 U、V、W の片道通路は U から V、V から U、V から W、W から U の4本です。列挙した向き以外には通れず、ループもありません。頂点の反復を許し、ちょうど2本の通路を通るとき、U から U、U から W、W から W の移動列をそれぞれ求め、通り数を整数で答えます。

行と列の順を U、V、W とし、行を出発、列を到着とすると次の行列です。U 行 V 列は1ですが、U 行 W 列は0です。向きを逆にして表を作らないよう、最初に各行を通路の一覧と照合します。

N = [ 0 1 0 ]
    [ 1 0 1 ]
    [ 1 0 0 ]

U 行 U 列 = 0・0 + 1・1 + 0・1
            = 1 通り
U 行 W 列 = 0・0 + 1・1 + 0・0
            = 1 通り
W 行 W 列 = 1・0 + 0・1 + 0・0
            = 0 通り

U の次に進めるのは V だけです。V から U に戻る U、V、U と、W に進む U、V、W がそれぞれ1通りあります。W からは U に進み、次は V に進むので、W に2辺で戻る列はありません。W、U、V が可能な2辺の列であることも、通路の向きに戻して確かめます。

無向の例では隣接点の数が往復数になりましたが、ここで W は U とつながっていても U から W へは通れません。向きのある場合、行きと帰りの両方が必要です。さらに、二乗の成分は2辺の移動列を数えるもので、距離や移動に要する時間を示すものではありません。2辺の列が存在しても、1辺の通路が存在するかどうかは別に隣接行列で調べます。

誤答を直す：対角を消さない

基本例題で「出発点と到着点が同じだから A 行 A 列は0」としたとします。隣接行列の対角が0という事実を、二乗にもそのまま移した誤りです。隣接行列の0は、A から A へ1辺で進むループがないことを表します。二乗では2辺を使えるため、意味が変わります。

図3のように A から B に進み、同じ辺を戻れば、2回の移動後に A へ着きます。辺を反復してよい条件に照らせば、これは有効な1通りです。さらに基本例題には C を経由する往復もあります。

修正するときは、図3の往復を頂点の列にして A、B、A と書き、辺 AB を2回使っていることを確かめます。次に A、C、A も書き加えます。積和では中継点 B と C の項がそれぞれ1です。対角成分の値2は、移動なしの1通りに往復を足した値ではありません。0辺の移動は今回の条件から外れます。

別の誤りは A 行と C 列を同じ位置ごとに並べず、行どうしを掛けることです。無向グラフでは対称性のため偶然同じ数になることもあり、間違いが見えにくくなります。有向の例で U から W と W から U をそれぞれ列挙し、行が出発、列が到着という約束に戻すと区別できます。W から U への2辺の列は存在しないので、U から W の1通りとは異なります。

練習問題

いずれも明示した辺以外はなく、ループと重複辺はありません。ちょうど2辺の移動列を数え、頂点と辺の反復を許します。答えは通り数を整数で示し、求めた移動列も書いてください。

1. 地点 D、E、F の無向辺は DE、EF です。D から F への移動列を求めてください。
2. 地点 G、H、J、K の無向辺は GH、GJ、GK です。G から G へ戻る移動列を求めてください。
3. 地点 L、M、N、O の無向辺は LM、LN、MO、NO です。L から O への移動列を求めてください。
4. 地点 T、X、Y の片道通路は T から X、X から Y、Y から T です。T から T への移動列を求めてください。
5. 地点 A、B、C、D の片道通路は A から B、A から C、B から D、C から D、D から A です。A から D への移動列を求め、行列の積和でも確かめてください。

練習の答えと解き方

1. D の次は E、E の次は F と進み、D、E、F の1通りです。DE と EF はどちらも指定された辺です。F に1回で行く辺はなく、ちょうど2回の条件にも合います。

2. G の次は H、J、K のいずれかです。それぞれ同じ辺を戻れるため、G、H、G と G、J、G と G、K、G の3通りです。各列の2本は指定された無向辺であり、辺の反復も許されています。

3. L の次は M または N です。いずれからも O へ進めるので、L、M、O と L、N、O の2通りです。中継点が異なるため重複せず、両列とも指定された2本の辺を使います。

4. T の次は X、その次は Y に限られます。T、X、Y は可能ですが T には戻らないので、求める列はなく0通りです。Y から T に進めば戻れますが、それは3辺の移動なので除きます。

5. A の次は B または C で、どちらからも D に進めます。A、B、D と A、C、D の2通りです。指定した矢印の向きも一致します。A、B、C、D の順に行と列を取ると、A 行と D 列の積和は次のとおりです。

A 行 D 列 = 0・0 + 1・1 + 1・1 + 0・0
            = 2 通り

中継点 B と C に対応する2項が、列挙した2つの列と一致します。D から A の矢印は、A から D への2辺の列を数える際には逆向きに使えません。

中継点を基準に分ける方法は、列挙の順序を決める手がかりにもなります。まず出発点から1回で行ける頂点を書き出し、それぞれから到着点へ進めるかを調べます。到着できなかった枝も記録に残すと、0の項がどの条件から生じたかを後で追えます。行列の積は、この確認を決まった順序でまとめたものです。

覚えておくこと

行を出発、列を到着とし、中継点の順序をそろえます。 2辺の移動列は中継点ごとの積を足して数えます。 二乗の対角成分には、条件が許す往復が入ります。 反復禁止や最短という条件は別に扱います。

つまずきを見分ける

答案では、最初に頂点の順序と、行・列に何を割り当てたかという書き込みを確かめます。次に積和の各項に中継点の名前を添え、0になった項について、前半と後半のどちらが通れないかを説明してもらいます。値だけ合っていても、この対応が逆なら有向の場面で破綻します。

個別指導で見るのは、列挙の記録と計算の記録の両方です。往復を消していた場合は、1回目と2回目の移動を順に指でたどり、反復を許すという問題文に戻します。反対に3辺の列を混ぜた場合は、頂点名の数ではなく隣り合う地点間の移動を2回数えます。答えの各項を実際の移動列に戻せれば、二段階の経路数の意味は明確になります。