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

解説

正解は3。隣接行列で1になっている組を拾うと、辺はa−b、b−c、b−d、c−d、c−e、e−fの6本である（無向グラフなので行列は対角線について対称になっている）。d−eは0なので辺がない。この6本だけをもち、d−eを結ばない図は3（ウ）である。

1（ア）は、b−cの辺がなく、行列にないd−eの辺がある。
2（イ）は、c−dの辺がなく、行列にないd−eの辺がある。
4（エ）は、6本の辺はそろっているが、行列にないd−eの辺が余分にある。

根拠：グラフの隣接行列による表現（i行j列が1ならノードiとjの間に辺がある）