高校数学C 重み付きグラフと経路—辺の本数と所要時間を分けて短い道を比べる｜武蔵野個別指導塾

乗換回数と所要時間を分け、候補の列挙と同率の判定を通して、重み付き経路を読み解きます。

よくあるのは、理系の高3が乗換回数の少ない道を見つけ、そのまま最短時間の道と決める場面です。乗換が少なくても、途中の区間に長い時間がかかれば、別の道の方が早く着くことがあります。辺の本数と辺に書かれた時間は別の量です。どの候補を比べたかを残し、足した時間とともに判断しましょう。

何を比べる問題か

出方の1つは、各区間の所要時間が書かれた図から、始点と終点を結ぶ道のうち最も短時間のものを選ぶ問題です。辺の本数が最小の道を選ぶ問題とは、比べる量が異なります。もう1つは、ある区間の時間が変わると最短の道がどう変わるかを調べる問題です。同じ時間になる境目では、最短の道が複数あります。さらに、図の数値を行列に並べたとき、通常の行列の積が最短時間を表すとは限らないことを説明する問題もあります。

ここでは辺の重みを正の所要時間とし、図に示された区間以外は直接移動できないものとします。特に断らなければ、辺は両方向に通れ、同じ2頂点の間に辺は1本、同じ頂点から自分自身への辺はありません。交差する線があっても、点を明示していなければそこで乗り換えられません。待ち時間や乗換時間は、問題に与えられた場合に限って別に加えます。

重みと道を読む

離散グラフでは、地点を頂点、直接つながる区間を辺で表します。辺に付けた数が重みです。図1のように、AとBの間の重み3は、その区間を通る時間が3分という意味です。線の長さや紙の上の角度が3分を表すわけではありません。AからCへBを経由すると、通った区間の時間を足して3 + 4 = 7分です。

図1ではAからCへの直接の辺にも9分とあります。直接の道は1辺、Bを経由する道は2辺ですが、所要時間はそれぞれ9分と7分です。辺の本数が少ないことと時間が短いことは一致するとは限りません。始点と終点が決まっていれば、通る頂点を順に書き、その隣同士が辺で結ばれているかを点検できます。

同じ頂点を繰り返さない道を、ここでは単純な道と呼びます。正の重みの場合、途中で同じ頂点へ戻る部分があれば、その閉じた部分には正の時間がかかります。そこを取り除いても前後は同じ頂点でつながり、時間は短くなります。したがって最短時間を探す際は単純な道を調べれば足ります。この理由は重みが正であることに依存します。重みが負の場合に同じ結論をそのまま使うことはできません。

道が存在しない場合は、候補の時間の最小値を計算できません。0分と書くと同じ地点にいる場合と区別できないため、「到達できない」と表します。候補を列挙するときには、終点に着いたらその候補を終え、辺のない頂点の組を続けて書かないことも必要です。

基本例題：直通と経由を比べる

図2の無向グラフで、AからDへ向かいます。各辺の数は分単位の所要時間です。AからDまでの単純な道をすべて挙げ、それぞれの時間を整数で求め、最短の道を答えてください。乗換に別の時間はかからないものとします。

図2の辺はABが2分、BDが7分、ACが4分、CDが3分、ADが10分です。BとCの間には辺がありません。Aを出た最初の行き先はB、C、Dのいずれかです。Bに進んだ後は、Aに戻ると頂点が重複し、Dへ進むほかありません。Cについても同様です。Dに直接進めばそこで終わるので、候補と時間は次のようになります。

A-B-D：2 + 7 = 9分
A-C-D：4 + 3 = 7分
A-D：10分

最小は7分で、最短の道はA-C-Dです。元の図へ戻すと、ACとCDはいずれも実際にある辺で、4分と3分の和も7分です。一方、直接のA-Dは1辺であり、他の候補の2辺より本数は少ないものの、時間は10分です。辺数の最小と時間の最小を同じ答えにしないよう、答えに単位と頂点列を添えます。

候補を漏らさないために、始点の隣から場合を分けました。隣接する地点を追い、すでに通った頂点に戻る枝を除き、終点に到達した枝を記録する手順です。到達できない枝も途中で止まったと記録すれば、見落としと区別できます。候補が大きく増える図では列挙が長くなりますが、ここでは小規模な図に絞って比較します。

標準例題：同じ時間の道

地点P、Q、R、Sを結ぶ無向グラフで、辺と所要時間はPQが3分、QSが5分、PRが5分、RSが3分、QRが2分です。他の辺はありません。PからSまでの単純な道をすべて挙げ、最短時間を整数の分で、最短の道を頂点列で答えてください。

Pの次はQかRです。Qへ進んだ場合、その次はSかRです。Rへ進んだ場合は対称にSかQへ進めます。それぞれSに着くまで追うと、候補は次の4本です。

P-Q-S：3 + 5 = 8分
P-Q-R-S：3 + 2 + 3 = 8分
P-R-S：5 + 3 = 8分
P-R-Q-S：5 + 2 + 5 = 12分

最短時間は8分で、P-Q-S、P-Q-R-S、P-R-Sの3本が同率です。2辺の道と3辺の道が同じ時間になることもあります。たとえばP-Q-R-Sは実在するPQ、QR、RSの3辺を通り、その内訳3分、2分、3分を足して8分です。1本を見つけて探索を終えると、残りの同率の道を落とします。

P-Q-Rと進んだ後にQへ戻る列は単純な道ではありません。しかもQRの往復には4分かかるため、正の重みの下では、その往復を取り除くと短くなります。単純な道に限定する理由と、同率の候補を漏らさず残す理由は別々に説明できます。

発展例題：時間が変わる境目

地点U、V、W、Xを結ぶ無向グラフの辺はUVが2分、VXが6分、UWが3分、WXが4分、UXがt分です。他の辺はなく、tは正の数です。UからXへの最短時間をtを使って表し、最短の道をtの範囲ごとに答えてください。乗換時間は加えません。

VとWの間には辺がないため、単純な道はU-V-X、U-W-X、U-Xの3本です。時間をそれぞれ計算します。

U-V-X：2 + 6 = 8分
U-W-X：3 + 4 = 7分
U-X：t分

最初の道は常に2番目の道より1分長く、最短にはなりません。残る7分とt分を比べます。

t < 7：最短時間はt分、道はU-X
t = 7：最短時間は7分、道はU-XとU-W-X
t > 7：最短時間は7分、道はU-W-X

たとえばt = 5なら直接の辺は5分で、経由の7分より短くなります。t = 7なら直接の辺とUW、WXの合計3 + 4がともに7分です。t = 9なら直接の辺は9分で、3 + 4 = 7分の経由が短くなります。境目を別に書けば同率を落とさずに済みます。なお、tは正なので、0以下の値はこの問題の条件に入りません。

候補の中に非常に長い道があっても、短い道を見つけただけでは列挙が完了したとは限りません。未知数を含む道は、値によって順位が変わるため、数を仮に1つ代入して比較を終えることもできません。まず各道の時間を文字の式のまま並べ、大小関係が変わる値を境に場合を分けます。等号の成立する場合は、両方の道が条件を満たすか元の辺へ戻って確認します。

また、道の時間は辺の時間の合計であり、中継地点そのものに付いた時間ではありません。もし乗換ごとに待ち時間が必要という条件が加われば、経由した回数に応じてその分を別に足してから比較し直します。元の条件にない待ち時間を勝手に加えることも、与えられた待ち時間を無視することも、別の問題を解くことになります。

誤答から直す：積と最小を混ぜない

基本例題で「A-Dは1辺だから最短時間は10分」とする答えは、辺の本数を時間の代わりに使っています。図3のように、直接の10分と経由の4 + 3 = 7分を同じ単位で比較して修正します。辺数を数える作業が失敗したわけではなく、求められた量の取り違えです。

別の誤りは、辺の重みを行列に入れ、その通常の積を最短時間と思うことです。基本例題で、行と列の順をA、B、C、Dとし、辺のない位置を0として重みを並べます。これは接続のない位置に0を置いた表であり、0分の辺があるという意味ではありません。

W =
0  2  4 10
2  0  0  7
4  0  0  3
10 7  3  0

通常の積W²のA行D列は、行と列の対応する成分を掛けて足します。

0・10 + 2・7 + 4・3 + 10・0
= 0 + 14 + 12 + 0
= 26

この26は2辺の道の時間9分と7分のどちらでもありません。通常の積は重みの積を足す演算であり、各道の重みの和を求めてから最小を選ぶ演算とは異なります。A-B-DとA-C-Dの各区間を足し、9分と7分を比べるのが時間を求める手順です。行列の数字を見て操作を決める前に、足し算と比較がそれぞれ何を表すか確かめましょう。

道がない箇所を0と置いた表では、0を時間として扱う失敗にも注意します。辺の有無は元の図と照合し、存在しない区間を0分で通れると考えません。移動できない場合と所要時間が小さい場合は、候補の有無から区別します。

練習問題

いずれも無向グラフで、示した辺以外はなく、重みは正の分単位の時間です。同じ頂点を繰り返さない道を調べ、乗換時間は加えません。時間は整数の分で答え、該当する道は頂点列で挙げてください。

1. 辺ABが6、BCが2、ACが11です。AからCへの各道の時間と最短の道を求めてください。
2. 辺DEが4、EFが5、DGが7、GFが2です。DからFへの各道と最短の道をすべて求めてください。
3. 辺HKが3、KLが4、HMが2です。HからLに行く道と、MからLに行く道の時間を求めてください。
4. 辺NPが2、PQが3、NQが8、QRが4です。NからRへの各道と最短の道を求めてください。
5. 辺STが5、TUが2、SUが9、VWが1です。SからUへの最短の道と、SからWへ到達できるかを答えてください。

練習の解答と解き方

1. A-Cは11分、A-B-Cは6 + 2 = 8分です。最短はA-B-Cの8分です。ABとBCの実際の2区間を足すと8分になり、直接の11分より短いと確認できます。

2. D-E-Fは4 + 5 = 9分、D-G-Fは7 + 2 = 9分です。最短は両方で9分です。Dからの選択肢はEとGで、それぞれ次にFへ進むので候補に漏れはありません。同率の片方だけを答えると不足します。

3. H-K-Lは3 + 4 = 7分です。M-H-K-Lは2 + 3 + 4 = 9分です。MからはHへ進む辺しかなく、HからLへはKを通るため、この頂点列が得られます。各辺の重みを元の条件に戻して足しています。

4. N-P-Q-Rは2 + 3 + 4 = 9分、N-Q-Rは8 + 4 = 12分です。最短はN-P-Q-Rの9分です。Rに入る辺はQRだけなので、Qまでの2通りを比べれば候補が尽くされます。辺数では直接N-Qを通る道が少なくても、時間は長くなります。

5. S-T-Uは5 + 2 = 7分、S-Uは9分です。最短はS-T-Uの7分です。VとWを結ぶ辺はありますが、S、T、Uの組とつながる辺がないため、SからWには到達できません。到達できないことを0分と表すことはできません。

覚えておくこと

• 頂点は地点、辺は直接通れる区間、重みは区間の時間です。
• 各道の時間は通る辺の重みを足し、候補の時間を比較します。
• 正の重みなら最短時間を単純な道の候補から探せます。
• 同率の道と到達できない場合を区別し、通常の行列積を最短時間と取り違えません。

つまずきの見分け方

答えが違ったときは、まず生徒が書いた頂点列と元の図を照合します。存在しない辺を使っていれば接続の読み取り、同じ頂点を繰り返していれば候補の条件を確認します。頂点列が正しければ、各辺の時間の転記と和を点検します。

個別指導では、列挙の途中の枝と、候補ごとの辺数・時間の記録を見ます。途中で探索を止めた枝に終点へ続く辺がないか、同じ最小値の候補を消していないかも尋ねます。最短という言葉の対象を辺数か時間かで言い直せれば、答えの根拠を自分の言葉で点検できます。道の比較は、条件と単位を添えた頂点列から始まります。