令和元年度 秋期 基本情報技術者試験 午前 問3
テクノロジ／基礎理論ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が図の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対応させて，ノード間にエッジが存在する場合は1で，エッジが存在しない場合は0で示す。
出典：令和元年度 秋期 基本情報技術者試験 午前 問3
- アグラフア
- イグラフイ
- ウグラフウ
- エグラフエ
正解：ウ
解説
隣接行列の1の位置を読み取ると，エッジは a-b，b-c，b-d，c-d，c-e，e-f の6本です（無向グラフなので行列は対角線に対して対称になります）。この6本の辺をもつグラフを選びます。ウは a-b，b-c，c-d，e-f の直線状の辺に，b-d と c-e の弧を加えた形で，ちょうど6本が一致します。
選択肢ごとの解説
- ア誤り。a-b，c-d，d-e，e-f，c-e，b-d の6本で，行列にない d-e があり，行列にある b-c がありません。
- イ誤り。a-b，b-c，d-e，e-f，c-e，b-d の6本で，行列にない d-e があり，行列にある c-d がありません。
- ウ正しい。a-b，b-c，c-d，e-f に加えて弧の b-d，c-e があり，隣接行列の6本の辺と完全に一致します。
- エ誤り。a-b，b-c，c-d，d-e，e-f，c-e，b-d の7本あり，行列にない d-e が余分です。