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

問題文

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

選択肢

ア：

イ：

ウ：（正解）

エ：

隣接行列から無向グラフを復元する問題【午前2 解説】

要点まとめ

結論：隣接行列の1を対として読み取り、エッジ集合は a–b, b–c, b–d, c–d, c–e, e–f であり選択肢はウです。
根拠：行列は対称で対角要素が0、各行・各列の1が対応する頂点間の無向辺を示しており重複を一度だけ数えます。
差がつくポイント：行や列を順に見て「既に数えた辺を重複カウントしない」ことと、水平線と半円の描写が表す具体的な辺を一致させる観察力です。

正解の理由

正解はウです。与えられた隣接行列から抽出される無向辺は次の通りです。

a と b が1 → a–b
b と c が1 → b–c
b と d が1 → b–d
c と d が1 → c–d
c と e が1 → c–e
e と f が1 → e–f

選択肢ウは水平直線で a–b, b–c, c–d, e–f を示し、上方半円で c–e を、下方半円で b–d を示しており、行列の1の位置と完全に一致します。

よくある誤解

行列の対称性を見落とし、a→b と b→a を別の有向辺と誤認する（無向は一度だけ数える）。
対角の0を見逃して自己ループ（a–a 等）があると誤解する。
図示の半円や直線を見て「必ず隣接する水平辺だけ」と考え、半円で示される非隣接辺を見落とす。

解法ステップ

隣接行列の各行を順に見る（例：行a, b, c, …）。
その行で値が1の列を見つけ、対応する頂点ペアをエッジとして記録する（例：行b の列cが1 → b–c）。
無向グラフなので (u,v) と (v,u) の重複を排除して一意に数える。
得られたエッジ集合を図の選択肢と照合する（水平辺や半円で示された結びつきと一致するか確認）。
補助として各頂点の次数を出すと検算に有効（今回は deg(a)=1, deg(b)=3, deg(c)=3, deg(d)=2, deg(e)=2, deg(f)=1）。

選択肢別の誤答解説

ア：水平直線が a–b, c–d, d–e, e–f とあるが行列では d–e が1ではなく、c–e が1のため不一致。
イ：水平に a–b, b–c, d–e, e–f があるが d–e は行列で0、c–d と c–e を適切に表現できていない。
ウ：水平 a–b, b–c, c–d, e–f と上方半円 c–e、下方半円 b–d の組合せが行列の1の位置と一致するため正解。
エ：隣接するすべての頂点間（連続直線で a–b–c–d–e–f）を示すが、行列では d–e が0でありエは過剰な辺を含む。

補足コラム

隣接行列は頂点数が多い場合に空間を多く消費しますが、"行列の対称性"と"対角要素"で無向グラフや自己ループの有無を即座に判定できます。コンピュータ処理ではエッジリストや隣接リストに変換して扱うことが多く、今回のような読み取りはその第一歩です。次数配列はグラフの基本的な性質（端点、連結性の手がかり）を与えます。

FAQ

Q1: 行列が対称でなければどうなる？
A1: 行列が対称でない場合は有向グラフ（辺に向きがある）を表している可能性が高く、その場合 (u,v) と (v,u) を別扱いします。

Q2: 対角に1があったらどう読む？
A2: 対角要素が1は自己ループ（頂点自身に戻る辺）を意味します。無向でも自己ループは特殊扱いになります。

Q3: 視覚図と行列が一致しないと感じたら？
A3: 各1 の位置を一覧化してエッジ集合を作り、図の各辺と照合する方法で確実に確認できます。

関連キーワード: 隣接行列、無向グラフ、エッジ集合、次数、グラフの可視化、行列対称性、隣接リスト、連結成分

← 前の問題へ次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！