高校数学C 有向グラフの表現—片道の条件を矢印にして行ける向きを読み取る｜武蔵野個別指導塾

片道の移動を矢印に直し、入次数と出次数、到達できない地点の調べ方を有向グラフでたどります。

よくあるのは、片道の矢印を逆にも進めると考える場面です。理系の高3が施設間の移動図を見て、AからBへ進む線を見つけたので、BからAへも戻れると答えます。しかし、矢印の先は到着側です。逆向きに進むには、別にBからAへの矢印が必要です。図形の位置よりも、どこからどこへ向かう線かを読み取る練習から始めます。

片道の図で何を問われるか

第1の型は、文章で与えられた移動の条件を図に移す問題です。地点を頂点、片道を向きのある辺で表し、出発と到着を逆にしないように描きます。双方向に移動できる区間は、互いに逆向きの2本で表します。線の交差は、それ自体を地点と指定しない限り乗換地点ではありません。

第2の型は、各地点から出る辺と入る辺の数を調べる問題です。出次数と入次数は頂点ごとに別々に数えます。ある頂点に線が何本接するかだけでは、向きの内訳が決まりません。図に描かれた辺を1本ずつ確認して、数えた印を記録すると見落としを防げます。

第3の型は、矢印に従って目的地まで行けるかを判定する問題です。直接つながっていなくても、途中の地点を経由して到達する場合があります。一方、線でつながっているように見えても、途中の矢印が逆を向いていれば、その並びでは進めません。ここでは所要時間や距離は扱わず、到達できるかどうかに注目します。

矢印の両端に役割を付ける

頂点と、出発点から到着点への向きを持つ辺で表したものを有向グラフといいます。AからBへの有向辺を、文章では「A→B」と書きます。矢印の根元が出発、先端が到着です。矢印を逆にしたB→Aは別の辺です。以下の例では、同じ向きの同じ2頂点を結ぶ辺の重複と、同じ頂点から同じ頂点へ戻る辺を置きません。

図1のように、A→BとB→Aの両方があれば、AとBの間はどちら向きにも1回で移動できます。B→Cは片道ですから、CからBへ1回で移ることはできません。図1では線の交差を頂点とせず、名前の付いた丸だけを地点とします。

図1でBに注目すると、Bから出る辺はB→AとB→Cの2本です。Bへ入る辺はA→Bの1本です。このように、頂点から出る辺の本数を出次数、その頂点に入る辺の本数を入次数といいます。次数は移動先の数ではなく辺の本数です。今回のように同じ向きの辺の重複がなければ、出次数は直接移動できる先の数にも一致します。

全頂点の出次数の和は辺の総数に等しく、入次数の和も辺の総数に等しくなります。なぜなら、各辺には出発点と到着点がそれぞれ1つあり、出次数の合計と入次数の合計にそれぞれ1回ずつ数えられるからです。この一致は検算に役立ちますが、一致しただけで個々の矢印が正しいとは限りません。向きを逆にしても、両方の和は変わらないからです。

到達の判定では、出発点から矢印をたどって順につないだ頂点の列を考えます。途中で同じ頂点や辺を再び通ってもよいものとします。ある地点に到達できたら、そこから出る矢印の先も到達できます。すでに調べた地点を再び調べる必要はありません。有限個の頂点について新たに加わる地点がなくなったとき、記録にない地点には到達できないと判断できます。

基本例題：展示室の移動

架空の展示室A、B、C、Dがあり、許される片道移動はA→B、A→C、B→C、C→B、C→Dです。これ以外の直接移動はありません。各室の出次数と入次数を整数で求め、AからDへ、またDからAへ移動できるか答えてください。到達するときは頂点の列を1つ示します。

図2のように各条件を矢印に直します。BとCの間には逆向きの2本がありますが、AとBの間にはA→Bしかありません。図2の矢印の先端を見て、各室の出入りを表にまとめます。

Aから出る辺はA→BとA→Cの2本です。Aへ入る辺はないため、Aの組は出次数2、入次数0です。Bから出るのはB→C、Bへ入るのはA→BとC→Bです。Cから出るのはC→BとC→D、Cへ入るのはA→CとB→Cです。Dから出る辺はなく、Dへ入るのはC→Dです。

辺の総数は5本です。表に戻って合計を確かめます。

出次数の和 = 2 + 1 + 2 + 0 = 5
入次数の和 = 0 + 2 + 2 + 1 = 5

両方とも5で、辺を数えた結果と合います。さらに各行を元の5本と照合しているので、合計だけでなく各室の内訳も確認できます。

AからDへは、たとえばA→C→Dと進めます。A→CもC→Dも条件にあるため、2回の移動がどちらも許されています。A→B→C→Dも到達を示す列ですが、到達の有無を答えるには1列で十分です。

DからAへは移動できません。Dから出る矢印が0本なので、最初の1回ができないためです。C→Dの線を逆にたどってD→Cとはできません。AからDに行ける事実は、DからAに戻れる証拠にはならないことに注意します。

標準例題：記録から到達できる地点を探す

架空の連絡所P、Q、R、S、Tについて、直接移動できる向きはP→Q、Q→R、R→Q、R→S、T→Sです。ほかの直接移動はありません。Pから出発して到達できる出発点以外の連絡所をすべて挙げ、Tに到達できるか答えてください。移動の回数に上限はなく、同じ連絡所を再訪してもよいものとします。

最初の記録はPです。そこから出る矢印を順に確認します。

Pから加わる地点：Q
Qから加わる地点：R
Rから加わる地点：S（Qは記録済み）
Sから加わる地点：なし

したがって、P以外で到達できるのはQ、R、Sです。QへはP→Q、RへはP→Q→R、SへはP→Q→R→Sという列が、それぞれ到達の証拠です。各隣接する2地点の矢印を条件に戻すと、いずれも許された向きです。

Tには到達できません。P、Q、R、Sから出る矢印をすべて調べても、Tに向かうものがないからです。T→SはTからSへの移動であり、SからTへの移動ではありません。RからQへ戻ることはできますが、Qを再び調べても新しい地点は増えません。到達できないという答えは、試した1本の列が失敗したというだけでなく、記録した地点の出口を調べ尽くしたことに支えられています。

もしS→Tという条件を1本追加すれば、P→Q→R→S→TでTにも到達します。逆にT→Sを追加しても、もともとある向きが重なるだけでPからTへ向かう出口にはなりません。変更する辺の向きまで明示してから、到達の範囲を調べ直します。

発展例題：一方向の連絡を加える

架空の作業地点U、V、W、Xに、U→V、V→W、W→U、W→Xの4本の片道連絡があります。既存の4本を残し、異なる2地点の間に既存の辺と重ならない有向辺を1本加えます。XからUに到達できるようにする追加辺をすべて挙げ、各場合について出次数と入次数が変化する地点を答えてください。移動の途中で地点を再訪してもかまいません。

まず、もとの図ではXから出る辺がないので、Xから最初の移動ができません。よって追加辺がXから出ない場合、Xは出発できず条件を満たしません。異なる地点への辺という条件の下で、候補はX→U、X→V、X→Wです。

それぞれを元の辺へ戻して調べます。

X→Uを追加：X→U
X→Vを追加：X→V→W→U
X→Wを追加：X→W→U

どの列も追加辺の後は既存の辺を向きどおりに通ります。候補以外の辺はXから出ないため、最初の移動ができず不適です。したがって答えはX→U、X→V、X→Wの3本です。候補を1つずつ試すだけでなく、Xから出る必要があると先に絞ることで、漏れがない理由も示せます。

出次数と入次数の変化は、追加辺の根元と先端に注目します。3通りともXの出次数が1増え、入次数は変わりません。先端がUならUの入次数、VならVの入次数、WならWの入次数がそれぞれ1増えます。先端の出次数は変わらず、ほかの地点の次数も変わりません。新しい辺の総数は5本なので、全体の出次数の和と入次数の和も、それぞれ4から5に増えます。

この結論は、追加できる辺が1本で、既存の辺を消さないという条件に基づきます。別の辺を消す操作や移動時間の比較まで、この結果から読み取ることはできません。例えばX→Vを加えた場合にXからUへ行けることと、その移動が短時間であることは別の主張です。

逆向きに読んだ答えを直す

基本例題で「DからCを通ってAに行ける」と答えたとします。図3のように、DとCを結ぶ線の存在だけを見ると、D→Cと読みたくなるかもしれません。しかし実際の矢印はC→Dです。DからCへ進む最初の移動が条件にありません。

原因は、接続しているという情報と、許される向きという情報を一緒にしていることです。修正するときは頂点の列を書き、隣り合う文字の間にある矢印を元の条件と1本ずつ照合します。D→Cが不一致なので、その列はここで止まります。Dから出る辺がほかにもないことまで調べれば、別の列でも出発できないとわかります。

反対に、矢印を1本ずつ正しく読んでも、直接の移動しか見なければ到達可能な地点を見落とします。基本例題のAからDへの直接の矢印はありませんが、A→C→Dと2本をつなげば到達できます。「直接行けない」と「どのようにたどっても行けない」は別の答えです。問題が求めるのが1回の移動か、回数を限定しない到達かを最初に確認します。

練習問題

次の5問はそれぞれ独立した架空の設定です。明記した矢印以外の直接移動はありません。同じ向きの辺の重複と、同じ地点へ戻る1本の辺はありません。到達の判定では移動回数を限定せず、地点や辺の再訪を許します。

1. 中継所A、B、CにA→B、C→B、C→Aがあります。Bの出次数と入次数を整数で答え、BからAへ到達できるか判定してください。
2. 室P、Q、R、SにP→Q、Q→P、Q→R、S→Rがあります。各室の出次数と入次数を整数で答え、両方の和を求めてください。
3. 拠点A、B、C、D、EにA→B、B→C、C→A、C→D、E→Dがあります。A以外でAから到達できる拠点をすべて挙げ、Eに到達できない理由を述べてください。
4. 場所P、Q、R、SにP→Q、Q→R、R→Pがあります。異なる2地点間の辺を1本追加してSからPに到達できるようにします。追加できる辺をすべて挙げてください。
5. 区画A、B、C、DにA→B、B→D、A→C、D→Cがあります。AからCへの直接移動の可否と、BからCへの到達の可否を答え、到達する場合は頂点の列を1つ示してください。

練習問題の解答と解き方

1. Bから出る辺は0本、Bに入る辺はA→BとC→Bの2本です。したがって出次数0、入次数2です。Bから最初の移動ができないので、BからAには到達できません。A→Bを逆向きに使っていないか、条件に戻して確認します。

2. Pは出1、入1、Qは出2、入1、Rは出0、入2、Sは出1、入0です。P→QとQ→Pは別々の辺として数えます。Q→RとS→Rも加えると、辺は4本です。

出次数の和 = 1 + 2 + 0 + 1 = 4
入次数の和 = 1 + 1 + 2 + 0 = 4

各辺の根元を出次数、先端を入次数に戻して数えると、表の各値と一致します。

3. 到達できるのはB、C、Dです。実際にA→B、A→B→C、A→B→C→Dで到達します。A、B、C、Dの出口を調べると、新しく加わる地点はありません。E→Dを逆向きに使えないため、Eには到達できません。

4. もとのSに出る辺がないため、追加辺はSから出る必要があります。候補はS→P、S→Q、S→Rです。それぞれS→P、S→Q→R→P、S→R→Pで条件を満たします。ほかの出発点を持つ辺ではSから動けないので、これらが全部です。

5. A→Cがあるので、AからCへ直接移動できます。BからCへもB→D→Cで到達できます。B→DとD→Cの両方が条件にあり、向きも合っています。B→Cという直接の辺はありませんが、到達の判定では途中にDを挟めます。

覚えておくこと

• 有向辺は根元から先端へ進み、逆向きは別の辺です。
• 出次数は出る辺、入次数は入る辺の本数です。
• 到達できることは、矢印に沿った頂点の列で示せます。
• 到達できないことは、到達済みの地点の出口を調べ尽くして示します。
• 出次数の和と入次数の和は、どちらも辺の総数に等しくなります。

つまずきを記録から見分ける

個別指導で確かめる際は、答えの丸や数字だけでなく、どの辺を数えたか、到達できる地点をどの順に記録したかを見ます。次数の合計が合っていても、逆向きの辺を取り違えて各頂点に配分した可能性があります。辺ごとに根元と先端を指し、出と入の欄へそれぞれ1回ずつ記録したかを確かめます。

到達できないと答えた場合は、調べた地点の出口が残っていないかを確認します。到達できると答えた場合は、書いた列の隣同士を条件へ戻します。矢印の向きと調査済みの地点が残る記録なら、結論の根拠を後からたどれます。