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

問題文

隣接行列

A

で表されるグラフはどれか。ここで、隣接行列とは、

n

個の節点から成るグラフの節点

V_{i}

と

V_{j}

を結ぶ枝が存在するときは第

i

行第

j

列と第

j

行第

i

列の要素が

1

となり、存在しないときは

0

となる

n

行

n

列の行列である。

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

選択肢

ア：

イ：

ウ：

エ：（正解）

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

隣接行列と無向グラフ【午前解説】

正解の理由

正解: エ
与えられた隣接行列 A は

0110100110010110

であり、1 に対応する非対角要素は (1,2),(1,3),(2,4),(3,4)（および対称な位置）です。したがって辺集合は {V1–V2, V1–V3, V2–V4, V3–V4} であり、選択肢エの図示（V1 が V2,V3 に接続、V4 が V2,V3 に接続、V2 と V3 は直接接続しない）が行列と一致します。

解法ステップ

行列の各行（または列）について、値が1の列番号を対応する隣接節点として書き出す。
得られた辺のリストを整理（重複を除く）し、グラフの辺集合を確定する。
各選択肢の図がその辺集合と一致するかを1辺ずつ照合する。
一致した選択肢が正解（今回の場合はエ）。

具体には第1行→V1はV2,V3に隣接、第2行→V2はV1,V4に隣接、同様に第3行→V3はV1,V4に隣接、第4行→V4はV2,V3に隣接。これを辺集合にまとめると {V1–V2,V1–V3,V2–V4,V3–V4} となる。

選択肢別の誤答解説

ア：V1 と V2・V3 の辺が描かれていないため、行列の第1行にある2つの1（V1–V2, V1–V3）と一致しない。
イ：図は完全な三角（V1–V2, V1–V3, V2–V3）およびV4が全ての頂点に接する形に見え、行列が示す V2–V3 の不在や V1–V4 の不在と矛盾する。
ウ：V4 が内部でV2,V3と接続していない（V4 は V1 のみと接続）ため、行列の (2,4) と (3,4) が1である事実と合わない。
エ：V1–V2, V1–V3, V2–V4, V3–V4 のみが描かれており、行列の1の位置と完全に一致するため正解。

よくある誤解

図の点の見た目（近さや中央配置）で辺の有無を判断してしまう。必ず行列の1の位置で判断すること。
行列が対称であるため「必ず完全グラフや輪になる」と誤解する。対称性は無向グラフを示すだけで辺の組合せは別問題です。
対角成分を自己ループと誤認する。対角が0なら自己ループはない点を見落としがちです。

補足コラム

与えられたグラフは実は4頂点のサイクル（C4）と同型です：順に V1–V2–V4–V3–V1 の閉路をなします。
隣接行列からは次数（degree）が簡単に得られます。ここでは各行の和が $2$ なので全頂点の次数が $2$ です（ $d (V 1) = d (V 2) = d (V 3) = d (V 4) = 2$ ）。
無向グラフの隣接行列は常に対称行列となり、自己ループは対角要素が1になる点を押さえておくと良いです。

FAQ

Q1: 隣接行列が非対称だったらどう判断する？
A1: 非対称なら有向グラフを表します。その場合 (i,j)=1 は有向辺 V_i→V_j を意味し、(j,i) の値は逆向きの存在を示します。

Q2: 行列の対角が1ならどう読む？
A2: 対角成分が1はその頂点に自己ループが存在することを示します。無向グラフでも自己ループは可能で、その扱いに注意が必要です。

Q3: 図の点の位置が違っても同じグラフかどうかを確かめるコツは？
A3: 辺集合（どの頂点ペアが接続されているか）だけを比較すること。配置や見た目は同型でも異なる描画になりますが、辺集合が一致すれば同一グラフです。

関連キーワード: グラフ理論、隣接行列、隣接リスト、無向グラフ、サイクルグラフ、次数、自己ループ

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！