平成24年度 春期 午前 問3

✓ これが正解エ（上記エのグラフ）

解説

行列の1の位置をそのまま枝の一覧に直します。

隣接行列は、第 i 行第 j 列が1なら節点 i と節点 j の間に枝があることを表します。設問の行列は対角線をはさんで対称ですから、行を上から順に読んで1が立っている列を書き出せば、枝の一覧がそのまま得られます。1行目は2列目と3列目、2行目は1列目と4列目、3行目は1列目と4列目、4行目は2列目と3列目です。同じ枝を二度数えないようにまとめると、枝は1番と2番、1番と3番、2番と4番、3番と4番の四本になります。判定の軸は二つです。枝の本数が四本になっているか、そしてその四本の組合せが一つ残らず一致しているかです。節点をどこに置いて描くかは答えを変えません。

ほかの選択肢はなぜ違うのか

• ア（上記アのグラフ）：本数は四本ですが、結び方が違います。1番と4番をつなぐ線が引かれ、2番と3番も直につながっていますが、行列ではこの二か所がどちらも0になっています。
• イ（上記イのグラフ）：四つの節点のあらゆる組合せが線でつながれており、線は六本あります。行列で0が並んでいる位置にも線が引かれているため、本数の時点で合いません。
• ウ（上記ウのグラフ）：1番から三方向へ線が伸びていますが、行列の1行目で1が立っているのは二か所だけです。4番につながる線も一本しかなく、行列が示す二か所と合いません。