ノードとノードの間のエッジの有無を，隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合，グラフで表現したものはどれか。ここで，ノードを隣接行列の行と列に対応させて，ノード間にエッジが存在する場合は1で，エッジが存在しない場合は0で示す。

選択肢

• アア：ノードをa,b,c,d,e,fの順に横一列に配置。直線で結ばれているのはa-b、c-d、d-e、e-f。b-c間は非連結。上側の弧でc-eを結び、下側の弧でb-dを結ぶ。
• イイ：ノードをa,b,c,d,e,fの順に横一列に配置。直線で結ばれているのはa-b、b-c、d-e、e-f。c-d間は非連結。上側の弧でc-eを結び、下側の弧でb-dを結ぶ。
• ウウ：ノードをa,b,c,d,e,fの順に横一列に配置。直線で結ばれているのはa-b、b-c、c-d、e-f。d-e間は非連結。上側の弧でc-eを結び、下側の弧でb-dを結ぶ。
• エエ：ノードをa,b,c,d,e,fの順に横一列に配置。直線で結ばれているのはa-b、b-c、c-d、d-e、e-f（すべて隣接ノードが直線で連結）。加えて上側の弧でc-eを結び、下側の弧でb-dを結ぶ。

正解と解説

正解：ウ ウ：ノードをa,b,c,d,e,fの順に横一列に配置。直線で結ばれているのはa-b、b-c、c-d、e-f。d-e間は非連結。上側の弧でc-eを結び、下側の弧でb-dを結ぶ。

隣接行列で1になっている位置がそのままエッジになる。この行列ではa-b、b-c、b-d、c-d、c-e、e-fの6本が存在し、d-eのエッジは存在しない。横一列に並べた図のうち、この6本を過不足なく描いたものが正解である。

選択肢ごとの解説

• アb-cのエッジが無く、行列に無いd-eを描いているため一致しない。
• イc-dのエッジが無く、行列に無いd-eを描いているため一致しない。
• ウ正解。描かれた6本のエッジが行列の1の位置と完全に一致する。
• エエッジが7本あり、行列に存在しないd-eを含むため誤り。

同じ分野の他の問題

• 図の2分探索木に1と0の二つの要素を順に追加したAVL木として，適切なものはどれか。2025年度 春期 午前 問6
• A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データ…2016年度 春期 午前 問5
• 次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の…2024年度 秋期 午前 問5
• 各ノードがもつデータを出力する再帰処理f(ノードn)を定義した。この処理を、図の2分木の根(最上位のノード)から始めたと…2024年度 春期 午前 問6
• 双方向リストを三つの一次元配列elem[i]、next[i]、prev[i]の組で実現する。双方向リストが図の状態のとき…2023年度 秋期 午前 問5