平成29年度 春期 応用情報技術者試験 午前 問3
テクノロジ／基礎理論ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対応させて，ノード間にエッジが存在する場合は1で，エッジが存在しない場合は0で示す。 a b c d e f a［0 1 0 0 0 0］ b［1 0 1 1 0 0］ c［0 1 0 1 1 0］ d［0 1 1 0 0 0］ e［0 0 1 0 0 1］ f［0 0 0 0 1 0］
出典：平成29年度 春期 応用情報技術者試験 午前 問3
- アグラフア
- イグラフイ
- ウグラフウ
- エグラフエ
正解：ウ
解説
隣接行列から，a-b，b-c，b-d，c-d，c-e，e-fの6本の辺をもつグラフが読み取れます。グラフウはa-b-c-dの直線的な接続に加えb-dの弧を持ち，さらにcからdの上を通ってeへ至る弧でc-eを表現しており，これらを合わせるとちょうど6本の辺が行列と一致します。
選択肢ごとの解説
- ア誤り。グラフアはb-cの辺がなくd-eの辺を含むなど，隣接行列とは異なる接続関係を表しています。
- イ誤り。グラフイはc-dの辺がなくd-eの辺を含むなど，隣接行列とは異なる接続関係を表しています。
- ウ正しい。グラフウはa-b，b-c，b-d，c-d，c-e，e-fの6辺をすべて満たし，隣接行列と一致します。
- エ誤り。グラフエはd-eの辺を余分に含んでおり，隣接行列にはない接続を表しています。