修了試験 2022-06-12実施分 基本情報技術者試験 問4

解説

正解は3です。 隣接行列では、行のノードと列のノードの交点が1なら、その2つのノードの間にエッジがあります。 無向グラフなので行列は対角線に対して対称になり、上半分だけ読めば全エッジが分かります。 行列から読み取れるエッジは、a－b、b－c、b－d、c－d、c－e、e－fの6本です。 d－eの交点は0なので、dとeの間にはエッジがありません。 【選択肢別解説】 1：× 選択肢1（図のア）はbとcが結ばれていません。 さらに、行列では0であるdとeの間にエッジが引かれています。 2：× 選択肢2（図のイ）はcとdが結ばれていません。 また、行列では0であるdとeの間にエッジがあります。 3：○ 選択肢3（図のウ）は、横並びのa－b、b－c、c－d、e－fに加え、上側の弧でcとe、下側の弧でbとdを結んでいます。 dとeの間は離れており、行列の6本のエッジと過不足なく一致します。 4：× 選択肢4（図のエ）は6本のエッジをすべて含みますが、dとeの間にも余分なエッジがあります。 行列のd行e列は0なので一致しません。 【ポイント】 隣接行列の問題は、まず1になっている組をすべて書き出してから図と照合します。 エッジが足りないものだけでなく、余分なエッジがあるものも除外する点が見落としやすいところです。