高校数学C 有向グラフの隣接行列—出発と到着を固定して矢印を数表へ移し替える｜武蔵野個別指導塾

片道の矢印を0と1で記録し、行和と列和から出入りを読み取るために使う有向隣接行列です。

よくあるのは、理系の高3が片道の移動を表に直すとき、行と列のどちらを出発地点にしたか取り違える場面です。図から数字を拾うことには慣れていても、表の右上の1がどちら向きの矢印を示すか説明しようとすると、手が止まります。数字の位置に出発と到着の名前を添えれば、方向を保ったまま表と図を行き来できます。

矢印と表の間で問われること

有向グラフは、地点などを表す頂点と、向きのある辺で関係を表したものです。辺の向きは矢印で示します。ここでは1本の矢印を1本の有向辺と呼びます。移動の場面なら、矢印の根元が出発、先端が到着です。以下の問題は自作の設定であり、同じ向きの辺の重複と、自分自身に向かうループを設けません。

出方の1つは、矢印の一覧から行列を作る問題です。各行を出発点、各列を到着点と決め、対応する矢印があれば1、なければ0を書きます。別の出方は、行列から矢印を復元する問題です。もう1つは行や列の和から、各頂点に出入りする辺の本数を調べる問題です。いずれも頂点を並べる順番を先に指定し、行と列に同じ順番を使います。

頂点の順番を変える場合は、行と列を同じ新しい順番に並べ替えます。行だけを入れ替えると、元の矢印の出発点だけが別の頂点になり、同じ関係を表せません。例えば最初に A、B、C と置いた表を C、A、B の順で書き直すなら、出発の見出しも到着の見出しも C、A、B にそろえ、各矢印をその名前に従って再配置します。表の数字の並びが変わっても、矢印の一覧が変わらなければ同じ関係です。

ここでの1は直接つながる矢印の有無を示します。途中の頂点を経由して到着できるかどうかを示す数字ではありません。また、辺の本数は移動時間や距離ではありません。図から表に移す前に、何を1とするかを確定する必要があります。

出発の行と到着の列を交差させる

頂点の順番を A、B、C とします。行列の成分は、まず行の頂点から出発し、次に列の頂点へ到着する矢印を見ます。例えば A から B への矢印は A 行 B 列の1です。B 行 A 列は逆向きの矢印を調べる別の場所です。片方が1でも、もう片方が1とは限りません。

図1のように、A 行と B 列の交点には A から B への矢印の有無を記録します。逆向きは B 行と A 列の交点に記録します。矢印の向きを逆にする操作は、この2か所の値を入れ替える操作に対応します。2か所がともに1なら、異なる2本の矢印が両方向にあります。

対角成分は出発と到着が同じ頂点の成分です。ループを除く今回の設定では対角成分は0です。ただし、一般にループを認める設定なら対角成分が1になることもあります。対角成分を見てから図を描くと、問題の条件に反した表を早く見つけられます。

ある行の和はその頂点から出る矢印の本数、すなわち出次数です。ある列の和はその頂点に入る矢印の本数、すなわち入次数です。1本の矢印は出発側の行和に1、到着側の列和にも1を加えます。そのため、全頂点の行和の合計と列和の合計はいずれも辺の総数に等しくなります。ただし、合計が一致しても、個々の矢印の向きが正しいとは限りません。

基本例題：3地点の連絡

地点 A、B、C をこの順に並べます。直接の連絡は A から B、A から C、B から C、C から A の4本です。ほかに矢印はなく、同じ向きの重複とループはありません。行を出発、列を到着とする隣接行列を求め、各地点の出次数と入次数を整数で答えてください。

図2のように、まず A を出発する矢印の先を見ます。A 自身への矢印はなく、B と C にはあるので、A の行は 0、1、1 です。B からは C への矢印があるため、B の行は 0、0、1 です。C からは A への矢印があるため、C の行は 1、0、0 です。行列を M とすると次のとおりです。

       到着 A B C
出発 A     0 1 1
     B     0 0 1
     C     1 0 0

行を横に足すと、出次数は順に次のようになります。

A: 0 + 1 + 1 = 2
B: 0 + 0 + 1 = 1
C: 1 + 0 + 0 = 1

列を縦に足すと、入次数は次のとおりです。

A: 0 + 0 + 1 = 1
B: 1 + 0 + 0 = 1
C: 1 + 1 + 0 = 2

答えは、A が出2本・入1本、B が出1本・入1本、C が出1本・入2本です。出次数の合計は 2 + 1 + 1 = 4、入次数の合計も 1 + 1 + 2 = 4 で、与えた矢印4本と一致します。さらに表の1を A→B、A→C、B→C、C→A と読み戻すと、元の4本に過不足がありません。和の一致に加え、1の位置を元の連絡に戻すことが方向の検算です。

標準例題：表から矢印を復元する

3つの部屋 P、Q、R の間の一方通行を、行と列をともに P、Q、R の順に並べて次の行列で表します。行が出発、列が到着です。ループと同じ向きの重複はありません。矢印を出発と到着の組で列挙し、各部屋の出次数と入次数を整数で求めてください。

       到着 P Q R
出発 P     0 0 1
     Q     1 0 1
     R     1 0 0

P 行の1は R 列にあるので P→R です。Q 行の1は P 列と R 列にあるので Q→P、Q→R です。R 行の1は P 列にあるので R→P です。P→R と R→P は別々の矢印であり、両方向に直接進めます。Q へ入る列には1がないので、どの部屋からも直接 Q へ入る矢印はありません。

出次数 P: 0 + 0 + 1 = 1
出次数 Q: 1 + 0 + 1 = 2
出次数 R: 1 + 0 + 0 = 1
入次数 P: 0 + 1 + 1 = 2
入次数 Q: 0 + 0 + 0 = 0
入次数 R: 1 + 1 + 0 = 2

出次数は P、Q、R の順に 1、2、1、入次数は 2、0、2 です。列挙した4本を出発別に数えると 1、2、1、到着別に数えると 2、0、2 となり、表の和と一致します。Q の入次数が0であることは Q から出られないことを意味しません。出る矢印と入る矢印は別々に確かめます。

発展例題：不足した成分を条件から決める

拠点 D、E、F の順に行と列を並べ、行を出発、列を到着とします。ループも同じ向きの重複もなく、各成分は0または1です。次の表で未知数 x、y、z を求め、矢印を列挙してください。ただし D の出次数は2、E の入次数は1、F の出次数は1です。答えは整数で示してください。

       到着 D E F
出発 D     0 x 1
     E     1 0 y
     F     z 0 0

まず D の行の和が2という条件を使います。次に E の列の和、最後に F の行の和を使います。

0 + x + 1 = 2
x = 1
x + 0 + 0 = 1
1 + 0 + 0 = 1
z + 0 + 0 = 1
z = 1

E の入次数の条件は x = 1 と同じ内容なので、y は決まりません。y は0または1のどちらも条件を満たします。したがって答えは x = 1、z = 1、y = 0 または1です。固定される矢印は D→E、D→F、E→D、F→D です。y = 1 の場合に限って E→F が加わります。

元の条件へ戻して確かめます。どちらの場合も D から出る矢印は E と F への2本、E に入る矢印は D からの1本、F から出る矢印は D への1本です。y に対応する E→F は、指定された3つの次数のいずれにも影響しません。条件の本数が未知数の個数と同じでも、独立した情報が足りなければ答えを1つに絞れないのです。

誤答を矢印に戻して直す

基本例題で、A から B への矢印を B 行 A 列に書く誤りを考えます。その数字が実際に示すのは B から A への矢印です。図3のように、出発と到着を逆に読むと、記録される向きも逆になります。

原因は、行と列を単に縦横の位置として覚え、地点の役割と結び付けていないことです。表の上に「列は到着」、左に「行は出発」と書き、矢印を声に出して読みます。A から B なら、まず A の行へ進み、次に B の列へ進みます。交点に1を書いたら、同じ位置から A→B と読み戻してください。

別の誤りは、A→B があれば B→A もあるとして対称な位置を両方1にすることです。双方向なら2本の矢印が必要です。図に逆向きがなければ B 行 A 列は0にします。すべての矢印を逆にしても行和の合計と列和の合計は一致するので、合計検算だけではこの誤りは発見できません。個別の1と矢印を対応させる作業が必要です。

練習問題

いずれも行は出発、列は到着で、同じ向きの辺の重複とループはありません。各頂点の順番は問題ごとに示したとおりです。行列と本数は整数で答え、矢印は出発→到着の形で書いてください。

1. 温室の区画 G、H、J をこの順に並べます。通路は G→H、H→J、J→H です。隣接行列と各区画の出次数、入次数を求めてください。
2. 倉庫 K、L、N の順の行列が次のとおりです。矢印を列挙し、各倉庫の出次数と入次数を求めてください。

出発 K   0 1 0
     L   0 0 0
     N   1 1 0
到着列   K L N

3. 中継所 U、V、W の順の表で、未知成分 a、b は0または1です。U の出次数が1、V の入次数が2のとき、a、b と矢印を求めてください。

       到着 U V W
出発 U     0 a 0
     V     0 0 1
     W     1 b 0

4. 展示室 S、T、X の順で、矢印は S→T、T→S、T→X、X→S です。T→X を取り除き、X→T を加えた後の行列と各室の出次数、入次数を求めてください。
5. 集積点 A、B、C、D の順で、矢印は A→B、A→D、B→C、C→A、C→D、D→B です。行列を作り、出次数と入次数が等しい頂点を求めてください。

練習の解答と解き方

1. G、H、J の行を順に作ります。G の行では H 列、H の行では J 列、J の行では H 列を1にします。

       到着 G H J
出発 G     0 1 0
     H     0 0 1
     J     0 1 0
出次数       1 1 1
入次数       0 2 1

3本を到着別に見ると G に0本、H に G と J から2本、J に H から1本です。行列の列和と一致します。

2. K 行の L 列、N 行の K 列と L 列が1です。矢印は K→L、N→K、N→L の3本です。

出次数 K: 0 + 1 + 0 = 1
出次数 L: 0 + 0 + 0 = 0
出次数 N: 1 + 1 + 0 = 2
入次数 K: 0 + 0 + 1 = 1
入次数 L: 1 + 0 + 1 = 2
入次数 N: 0 + 0 + 0 = 0

出次数は順に 1、0、2、入次数は 1、2、0 です。矢印を出発別と到着別に直接数えても同じです。L の行が零でも、L の列に1があるため到着は可能です。

3. U の行の和と V の列の和を順に使います。

0 + a + 0 = 1
a = 1
a + 0 + b = 2
1 + b = 2
b = 1

矢印は U→V、V→W、W→U、W→V です。U から出るのは V への1本で、V に入るのは U と W からの2本です。与えられた条件に戻ります。

4. 変更後の矢印は S→T、T→S、X→S、X→T です。取り除く成分と追加する成分は異なる行と列にあります。

       到着 S T X
出発 S     0 1 0
     T     1 0 0
     X     1 1 0
出次数       1 1 2
入次数       2 2 0

出発別に1、1、2本、到着別に2、2、0本です。変更前に存在した T→X が消え、逆向きが加わったことも表から読み戻せます。

5. 出発ごとに矢印を整理すると、A は B と D、B は C、C は A と D、D は B へ向かいます。

       到着 A B C D
出発 A     0 1 0 1
     B     0 0 1 0
     C     1 0 0 1
     D     0 1 0 0
出次数       2 1 2 1
入次数       1 2 1 2

同じ頂点について比べると、A は2と1、B は1と2、C は2と1、D は1と2です。よって該当する頂点はありません。出次数の合計も入次数の合計も6であり、元の矢印6本に一致します。

覚えておくこと

行は出発、列は到着と固定し、頂点の並びを記します。
矢印がある位置を1、ない位置を0にします。
行和は出次数、列和は入次数です。
合計とともに、各1を元の矢印に戻して調べます。

つまずきの見分け方

表の数字が合わないときは、完成した答えだけでなく、最初の1をどこから拾ったかという途中の記録を見ます。1本の矢印に対して、行の見出しと列の見出しを指しながら出発と到着を言えるかが手がかりです。個別指導では、逆向きの成分を別に尋ね、0を置いた理由も確かめます。

行和と列和を取り違えた場合は、1つの頂点から出る矢印に印を付け、表のどの1に対応するかを追います。合計が合っていても向きを逆に書くことはあるため、数値だけで終えず、矢印を描き戻した記録まで照合します。行と列の役割を固定すると、方向を持つ関係を表の中でも追えます。