平成29年度春期 応用情報技術者試験 午前 問3

正解：ウ

AI解説

正解はウ。隣接行列は、行と列にノードを対応させ、ノードiとノードjの間にエッジがあれば成分(i,j)を1、なければ0とする表現である。無向グラフでは行列は対称になる。解き方は、行列の各行の1の個数（=各ノードの次数、つながっているエッジの数）を数え、各選択肢のグラフのノードの次数および接続関係と照合すればよく、一致するのはウのグラフである。 ア: 図中のグラフは、隣接行列が示すエッジの有無（ノード間の接続関係）と一致しない箇所があるため誤りである。 イ: 図中のグラフは、一部のノードの次数（接続エッジ数）が隣接行列と食い違うため誤りである。 ウ: 正しい。全ノードの次数と接続関係が隣接行列の1の位置と完全に一致するグラフである。 エ: 図中のグラフは、行列で0となっているノード間にエッジがあるなど、対応が取れないため誤りである。 💡 隣接行列の問題は「各行の1の個数=そのノードの次数」をまず数えて選択肢を絞り、残った候補だけ個々のエッジを照合すると速い。無向グラフなら行列が対称であることも確認ポイント。