高校数学C 隣接行列の作り方—頂点の順序を決めて接続を成分に写し取る｜武蔵野個別指導塾

頂点の順序を変える際の行と列の対応や、辺の有無を表すのが隣接行列です。

よくあるのは、理系の高3が頂点を表す行と列を途中で別々の順序に変えてしまう場面です。図では同じ辺を見ているつもりでも、行の見出しと列の見出しがずれると、1が示す接続先は変わります。数字の並びが対称に見えるかだけではなく、各数字がどの頂点の組を表すかまで戻って確かめましょう。

要点（結論から）

• 頂点の順を決め、行と列に同じ順で見出しを付けます。
• 異なる2頂点の間に辺があれば1、なければ0です。
• 単純無向グラフでは対角成分は0で、行列は対称です。

接続を表に移す問い

出方の1つは、頂点と辺が与えられた図から隣接行列を作る問題です。頂点の順序を先に決め、辺がある組に1、ない組に0を書きます。図の線の長さや頂点の位置は、接続の有無を変えません。線が交差する場合も、交点を頂点と指定していなければ、そこで辺がつながるとは読みません。

2つ目は、0と1の行列から辺を復元する問題です。行と列の見出しを付けてから、異なる2頂点の組を取り出します。対称な位置にある2個の1は、向きのない同じ1本の辺に対応します。2本の辺として数えないことがポイントです。

3つ目は、頂点の順番を変えた表や、不完全な表を調べる問題です。行と列を同じ順に並べ替えると、同じグラフを別の配列で表せます。対角成分が0で、対角線を挟んだ成分が一致することは必要ですが、頂点名を固定したときに元の接続と同じかどうかは、対応する組ごとに調べる必要があります。

ここでは、頂点自身を結ぶループも、同じ2頂点を結ぶ重複した辺もない無向グラフを扱います。辺には向きや重みを付けません。行列の積による移動回数の数え方には進まず、1つの成分が直接の接続を表すところに焦点を当てます。

行と列が表す頂点の組

頂点は場所やものを表す点、辺は2つの頂点の直接の接続を表す線です。無向とは、辺の両端を入れ替えても同じ接続とみなすことです。単純という条件の下では、異なる2頂点の間には辺が高々1本あり、頂点から自分自身への辺はありません。

図1のように、頂点 P、Q、R の順を行と列の両方に付けます。辺は PQ と QR の2本です。例えば P と Q は直接つながるので、P 行 Q 列に1を書きます。無向なので Q 行 P 列にも1が入ります。一方、P と R の間に直接の辺はないので、その2か所は0です。Q を経由して行けることと、直接の辺があることは別です。

図1では、P 行 P 列など同じ頂点を指定する位置も0です。これらを対角成分と呼びます。行列を左上から右下へたどる対角線を挟んで、P 行 Q 列と Q 行 P 列のように値が一致する性質を対称性といいます。単純無向グラフから作る隣接行列は、対角成分が0の対称な0・1行列です。

逆に、行と列に同じ順で頂点名を付けた正方行列が、0と1からなり、対角成分が0で対称なら、それを単純無向グラフに戻せます。対角線より上の1を1個ずつ見て、その行と列の頂点を1本の辺で結びます。下側の1は同じ辺を反対側から記録したものです。対角線より上の0は、その頂点の組に辺がないことを表します。

行を出発、列を到着として読んでも、無向の辺では逆向きにも同じように対応します。ただし、行の成分がすべて0になる頂点もありえます。その頂点には辺が接続しておらず、孤立点です。行と列がすべて0でも頂点そのものを消してはいけません。

基本例題：通路の図を行列にする

4つの展示場所 A、B、C、D を頂点とし、直接の通路を辺とします。通路は AB、AC、BC、CD の4本です。通路に向きはなく、同じ場所への通路や重複はありません。頂点の順を A、B、C、D として隣接行列を求め、辺の一覧に戻して確かめなさい。図2はこの条件を描いたものです。

図2の A は B、C と直接つながり、D とは直接つながりません。そこで A 行は、列の順に 0、1、1、0 です。A から C を通って D に行けても、A 行 D 列は0のままです。B 行と C 行も同じように直接の通路だけを見ます。

A 行: 0 1 1 0
B 行: 1 0 1 0
C 行: 1 1 0 1
D 行: 0 0 1 0

したがって、行と列の順をともに A、B、C、D とすると、求める行列は次です。

    A B C D
A   0 1 1 0
B   1 0 1 0
C   1 1 0 1
D   0 0 1 0

検算では、対角線より上の6か所を順に読みます。AB、AC、AD、BC、BD、CD に対応する値は、順に 1、1、0、1、0、1 です。よって1となる組は AB、AC、BC、CD で、元の4本に戻りました。対角成分はすべて0で、対称な位置の値も一致します。

行の和を数えると A、B、C、D の順に 2、2、3、1 です。これは各頂点につく辺の本数と一致します。行和の合計が8なのは、1本の辺を両端で1回ずつ数えるためです。ただし、行和が合うだけでは辺の相手まで確定しません。元の辺の一覧と照らす点検も必要です。

標準例題：表から接続を復元する

4つの作業地点 K、L、M、N の隣接行列が次で与えられています。行と列の順はともに K、L、M、N です。単純無向グラフとして、辺を重複なく列挙し、孤立点の有無を答えなさい。

    K L M N
K   0 1 0 1
L   1 0 1 0
M   0 1 0 1
N   1 0 1 0

対角成分は0で、対角線を挟んだ値は一致します。そこで上側の成分を読み、各組を1回ずつ調べます。

KL: 1 → 辺がある
KM: 0 → 辺がない
KN: 1 → 辺がある
LM: 1 → 辺がある
LN: 0 → 辺がない
MN: 1 → 辺がある

答えは KL、KN、LM、MN の4本です。K には KL と KN、L には KL と LM、M には LM と MN、N には KN と MN がつくので、孤立点はありません。

辺の一覧から行列へ戻すと、K 行は L と N に対応する位置が1で、0、1、0、1 です。同様に L、M、N の行も元の表と一致します。例えば L 行 K 列の1を KL とは別の辺と数えると、同じ通路を二重に記録してしまいます。

発展例題：並べ替えと欠けた値

4頂点 U、V、W、X の単純無向グラフについて、U、V、W、X の順に行と列を置いた隣接行列の一部が次です。a、b、c は0または1で、辺の本数は3本です。a、b、c を求め、次に頂点の順を W、U、X、V に変えた行列を求めなさい。

    U V W X
U   0 1 a 0
V   1 0 0 b
W   1 0 0 1
X   0 c 1 0

対称性により、U 行 W 列と W 行 U 列、V 行 X 列と X 行 V 列がそれぞれ等しくなります。

a = 1
b = c

対角線より上の6か所の和は、辺の本数に等しくなります。それぞれの辺をちょうど1回数えるからです。

1 + a + 0 + 0 + b + 1 = 3
1 + 1 + b + 1 = 3
b = 0
c = 0

よって辺は UV、UW、WX です。新しい順では、各行について接続先を新しい列順 W、U、X、V で読み直します。

W 行: 0 1 1 0
U 行: 1 0 0 1
X 行: 1 0 0 0
V 行: 0 1 0 0

    W U X V
W   0 1 1 0
U   1 0 0 1
X   1 0 0 0
V   0 1 0 0

新しい表の上側からは WU、WX、UV の3本が出ます。WU は元の UW と同じ無向辺なので、元の条件に戻りました。行と列を同時に動かしたため、各1の場所は変わっても頂点名の組は変わりません。

もし辺の本数が与えられなければ、a = 1 と b = c までは決まりますが、b は0と1のどちらも可能です。対称性だけで欠けた値が必ず全部決まるわけではありません。また、辺の本数が4本という条件なら b = c = 1 となります。この分かれ目を、図形の見た目ではなく残った頂点の組で判断します。

順序を片側だけ変えた誤答

基本例題の行列で、A と B の行だけを交換し、列は A、B、C、D のままにしたとします。図3のように、最初の行は元の B 行ですが、その行に A という見出しを付け直すと、A 行 A 列が1になります。

図3の誤答は次の配列です。元の接続を保った行列ではありません。

    A B C D
A   1 0 1 0
B   0 1 1 0
C   1 1 0 1
D   0 0 1 0

原因は、行の数字を移した後で、行の見出しと数字の対応を失ったことです。A 行 A 列の1は、単純グラフでは認めない A 自身への辺を意味してしまいます。さらに A 行 B 列は0になり、元の AB を失います。対角成分を0に書き直すだけでは、失われた AB は復元できません。

修正するには、行の並びを B、A、C、D としたとき、列も B、A、C、D とします。元の B 行を新しい列順で読むと、B、A、C、D に対して 0、1、1、0 です。元の A 行は 1、0、1、0 になります。

    B A C D
B   0 1 1 0
A   1 0 1 0
C   1 1 0 1
D   0 0 1 0

この表からは BA、BC、AC、CD が得られ、元の4本に一致します。別の場合には、片側だけの入れ替えでも対角成分が0で対称な表が偶然できることがあります。その場合も頂点名の付いた辺の一覧まで戻らなければ、元と同じ接続かは判定できません。

練習問題

いずれも自作の単純無向グラフで、辺の向き、重複、ループはありません。行と列には指定された同じ順を使い、行列で答えるときは見出しも書きなさい。

1. 頂点 E、F、G、H の辺が EF、EG、FH です。E、F、G、H の順の隣接行列を求め、辺の一覧に戻しなさい。
2. 頂点 J、K、L、M の順の隣接行列が次のとき、辺を重複なく列挙し、孤立点を答えなさい。

    J K L M
J   0 1 1 0
K   1 0 1 0
L   1 1 0 0
M   0 0 0 0

3. 頂点 S、T、U の順の行列が次です。単純無向グラフの隣接行列となるように、0または1の x、y、z を求め、辺を列挙しなさい。

    S T U
S   0 1 x
T   1 y 0
U   1 z 0

4. 頂点 A、B、C、D、E の辺が AB、BC、CD、DE です。E、C、A、D、B の順の隣接行列を求め、辺の本数を表から確かめなさい。
5. 頂点 P、Q、R、S の順の表の上側が、PQ = 1、PR = 0、PS = 1、QR = 1、QS = 0、RS = 1 です。対角成分がすべて0で対称な表を完成し、P と R が直接つながるか答えなさい。

練習問題の解答と解き方

1

各辺の両端に1を入れ、その他を0にします。

    E F G H
E   0 1 1 0
F   1 0 0 1
G   1 0 0 0
H   0 1 0 0

上側の1は EF、EG、FH にあり、元の3本に戻ります。例えば G と H はともに別の頂点につながっていますが、互いを結ぶ辺は与えられていないので GH は0です。

2

上側を J から順に読むと、JK、JL、KL が1です。他の組は0なので、辺はこの3本です。M の行と列は0で、M が孤立点です。列挙した3本から表を作り直すと、J、K、L の各行の1が2個、M の行の1が0個となり、与えられた表に戻ります。

3

対称な位置と対角成分を照らします。

x = 1
y = 0
z = 0

完成した表の上側で1となるのは ST と SU です。逆に ST と SU を両方向の位置に書けば、元の指定された成分も含めて表に戻ります。y は T 自身との組なので、対称性だけではなくループがない条件から0と決めます。

4

新しい順で各頂点の隣を調べます。E は D、C は B と D、A は B、D は C と E、B は A と C に接続します。

    E C A D B
E   0 0 0 1 0
C   0 0 0 1 1
A   0 0 0 0 1
D   1 1 0 0 0
B   0 1 1 0 0

対角線より上の1は ED、CD、CB、AB の4個です。無向辺の端の順序をそろえると AB、BC、CD、DE となり、指定された4本と一致します。頂点を並べ替えても辺の本数は変わりません。

5

下側を上側と対称にし、対角成分を0にします。

    P Q R S
P   0 1 0 1
Q   1 0 1 0
R   0 1 0 1
S   1 0 1 0

P 行 R 列は0なので、P と R は直接つながりません。表から辺を拾うと PQ、PS、QR、RS で、指定された上側の6個の値にも戻ります。P と R の間に別の頂点を通る移動があっても、直接の接続を示す0は変わりません。

要点

• 頂点の順を決め、行と列に同じ順で見出しを付けます。
• 異なる2頂点の間に辺があれば1、なければ0です。
• 単純無向グラフでは対角成分は0で、行列は対称です。
• 辺の一覧は対角線より上を読み、並べ替えは行と列を同時に行います。
• 最後に頂点名の組へ戻して、元の接続と照合します。

どこで対応がずれたか

図から表を作る途中の記録を見て、最初に頂点の順を行と列の両方に書いたかを確かめます。次に、1つの1を指して、その行と列の頂点を答えられるかを見ます。答えが図の辺と合わなければ、成分の位置から頂点名へ戻る練習をします。

対角成分と対称性は合っているのに辺が違う場合は、組の対応か並べ替えの過程を追います。個別指導では、元の辺の一覧、途中の見出し、完成した表を並べ、どの段階で対応が変わったかを確認します。行列の1は、名前の付いた2頂点を結ぶ記録です。