応用情報技術者 2017年 春期 午前2 問03

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

正解の理由

解法ステップ

1. 隣接行列の行 i 列 j の値が1ならノード i と j の間に辺があると読む（無向グラフなので行列は対称で、i→j と j→i が両方1になる）。
2. 対角成分が0なら自己ループはないと判断する。
3. 重複を避けるため上三角（i < j）の成分だけ確認し、辺の集合を列挙する。
4. 列挙した辺集合と各選択肢の辺集合を比較し、一致する図を選ぶ。

選択肢別の誤答解説

• ア：実線として a―b, c―d, d―e, e―f を挙げているが、実際の行列では d―e は存在しない（d と e の位置は0）。一方で行列にある b―c の辺がアの実線では欠けている。曲線として b―d と c―e を持つ点は合っているが、実線集合がずれているため不一致となる。したがってアは誤り。
• イ：実線が a―b, b―c, d―e, e―f となっているが、ここでも d―e が余分かつ本来必要な c―d が抜けているため不一致。
• ウ：実線 a―b, b―c, c―d, e―f と曲線 b―d, c―e の組合せが、隣接行列から列挙される辺集合と完全に一致するため正しい。
• エ：実線として a―b, b―c, c―d, d―e, e―f を挙げているが、d―e が実際には存在しない（行列の該当成分は0）ため誤り。

よくある誤解

• 行列を行方向だけで読んで「有向辺」として扱うミス：無向グラフでは行列は対称で、片方だけ見て決めないこと。上三角または下三角だけを見れば重複を避けられる。
• 図の「実線」と「曲線」をタイプの異なる辺と混同する：本問ではいずれも単なる辺の表現であり、種類に差はない。重要なのはどの頂点ペアが結ばれているかだけ。
• 選択肢の辺を読み違えて「辺がある/ない」を逆に解釈する（特に複数の近接頂点がある場合に見落としがち）。

補足コラム

A = [
 [0,1,0,0,0,0],
 [1,0,1,1,0,0],
 [0,1,0,1,1,0],
 [0,1,1,0,0,0],
 [0,0,1,0,0,1],
 [0,0,0,0,1,0]
]
nodes = ['a','b','c','d','e','f']
edges = []
n = len(A)
for i in range(n):
    for j in range(i+1, n):
        if A[i][j] == 1:
            edges.append((nodes[i], nodes[j]))
print(edges)  # [('a','b'),('b','c'),('b','d'),('c','d'),('c','e'),('e','f')]

FAQ