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

隣接行列で1になっている組（行列は対称なので上半分だけ見ればよい）を拾うと，エッジは次の6本です。

a−b，b−c，b−d，c−d，c−e，e−f

d−e のエッジは存在しない（d行e列が0）ことに注意します。

• ア: ア
  誤り。b−c のエッジがなく，存在しないはずの d−e のエッジがあります。

• イ: イ
  誤り。c−d のエッジがなく，存在しないはずの d−e のエッジがあります。

• ウ: ウ
  正しい。a−b，b−c，c−d，b−d（下の弧），c−e（上の弧），e−f の6本で，隣接行列と完全に一致します。

• エ: エ
  誤り。必要な6本のエッジに加えて，存在しないはずの d−e のエッジがあります。

答え

ウ: ウ