基本情報技術者 2019年秋期午前（科目A）問03

問題文

ノードとノードの間のエッジの有無を、隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合、グラフで表現したものはどれか。ここで、ノードを隣接行列の行と列に対応させて、ノード間にエッジが存在する場合は1で、エッジが存在しない場合は0で示す。

🖊️ 解答を隠して解いてみる

選択肢

ア：

イ：

ウ：（正解）

エ：

🔒 解説は解答すると表示されます

隣接行列からの辺復元【午前解説】

正解の理由

隣接行列を上三角だけ（行番号 < 列番号）で読み取ると、1の位置がそのまま無向辺を示します。本問の行列から抽出される辺はa–b、b–c、b–d、c–d、c–e、e–fの6本です。選択肢の描画を比較すると、これら6本を正確に表現しているのはウの図だけです。したがって正答はウです。

（抽出した辺の集合：{a-b, b-c, b-d, c-d, c-e, e-f}）

解法ステップ

隣接行列が無向グラフなので行列は対称で、対角成分は自己ループの有無を示す（ここでは全て0）。
辺の一覧は上三角（行 < 列）だけを見ればよい。行・列の交点が1ならその2頂点間に辺がある。
上三角を順に読むと、1がある位置から辺を列挙する（例：行a列bが1ならa–b）。
列挙した辺集合と各選択肢の辺集合を比較し、完全一致する選択肢を選ぶ。

簡潔に言えば「行列→上三角→辺リスト作成→選択肢と照合」です。

選択肢別の誤答解説

ア
- アは水平直線にa–bとc–d、d–e、e–fを置いていますが、行列にはd–eの辺がなく代わりにb–cやb–dが存在します。したがってアはb–cを欠き、誤ってd–eを含んでいる点で不一致です。
イ
- イはc–eとb–dを含む点は正しいものの、c–dを欠き、代わりに誤ってd–eを含んでいます。正しいグラフにはc–dが存在しd–eは存在しないため、イは辺集合が一致しません。
ウ
- ウは水平辺としてa–b, b–c, c–d, e–fを、さらに上方半円でc–e、下方半円でb–dを描いており、列挙した辺集合と完全に一致します。ゆえに正解はウです。
エ
- エは隣接するすべての頂点間（a–b, b–c, c–d, d–e, e–f）を繋いでおり、これによりd–eを含んでいます。しかし行列ではd–eは0であり存在しないためエは不適切です。

よくある誤解

対角成分の1を自己ループと誤認する
- 試験問題では自己ループが明示されていなければ対角は通常0。対角を見て慌てて辺を追加しないこと。
全行列を二重に読む（上下両方で数える）
- 無向グラフの隣接行列は対称なので上三角だけを見ればよい。上下両方を見て重複して数えるミスが多い。
図の描画方向（上方半円・下方半円）を読み違える
- 図の曲線がどの2頂点を結ぶかを丁寧に確認する。誤った辺の有無だけで選択肢が変わることが多い。

補足コラム

実務・アルゴリズム観点では、稀に大規模グラフでは隣接行列より隣接リスト表現の方がメモリ効率が良いです。ただしこの種の試験問題では隣接行列が与えられたら、まず対称性と上三角を利用して素早く辺を抽出するのが解法の王道です。
手早く処理するコツ：上三角を左上から右下に向かって走査し、1を見つけたら即座にその対応辺をメモする習慣をつけると時間短縮になります。

FAQ

Q1. 有向グラフだったらどう見る？
A1. 有向グラフなら行列は一般に非対称になり、行i列jが1ならi→jの向きの辺がある。上三角だけで済ますことはできないので全体を確認します。

Q2. 自己ループがある場合の読み方は？
A2. 対角成分（行i列i）が1なら頂点iに自己ループがあると読みます。問題文で自己ループが想定されているか注意してください。

Q3. 手計算ではなくプログラムで変換するには？
A3. 下記の簡単なPython例のように上三角を走査して辺を列挙できます。

# adjacencyは2次元リスト（行列）で与えられるとする
nodes = ['a','b','c','d','e','f']
edges = []
n = len(nodes)
for i in range(n):
    for j in range(i+1, n):
        if adjacency[i][j] == 1:
            edges.append((nodes[i], nodes[j]))
print(edges)