令和元年度 秋期 基本情報技術者試験 問3

解説

正解は3です。 隣接行列で1になっている組を拾い出し、そのエッジだけを持つグラフを選ぶ問題です。 無向グラフなので行列は対角線に対して対称であり、上半分だけを見れば十分です。 隣接行列から読み取れるエッジは次の6本です。 a行ではbの列だけが1なので、a-bがあります。 b行ではcとdの列が1なので、b-cとb-dがあります。 c行ではdとeの列が1なので、c-dとc-eがあります。 e行ではfの列が1なので、e-fがあります。 d-eの位置は0なので、dとeの間にエッジはありません。 【選択肢別解説】 1：× 図のアは、a-b、c-d、d-e、e-f、cとeを結ぶ上の弧、bとdを結ぶ下の弧で構成されています。 b-cのエッジがなく、行列にないd-eのエッジがあるので誤りです。 2：× 図のイは、a-b、b-c、d-e、e-f、cとeを結ぶ弧、bとdを結ぶ弧で構成されています。 c-dのエッジがなく、d-eのエッジがあるので誤りです。 3：○ 図のウは、a-b、b-c、c-d、e-f、cとeを結ぶ上の弧、bとdを結ぶ下の弧で構成されています。 dとeの間は離れていて、行列の6本のエッジと過不足なく一致します。 4：× 図のエは、選択肢3（図のウ）のエッジに加えてd-eもつながっています。 行列ではd-eは0なので、エッジが1本多く誤りです。 【ポイント】 隣接行列の問題は、まず1の位置からエッジを一覧にし、選択肢との差分（不足と余分）を探すと確実です。 無向グラフの隣接行列は必ず対称になることも確認に使えます。