修了試験 2021-01-24実施分 基本情報技術者試験 問3

解説

正解は3です。 隣接行列は、行と列が交わる位置が1ならそのノード間にエッジがあることを表します。 無向グラフなので行列は対角線に対して対称になり、上半分だけを読めば全エッジが分かります。 【隣接行列の読み取り】 a行はb列だけが1なので、エッジはa-bです。 b行はa、c、d列が1なので、新たなエッジはb-cとb-dです。 c行はb、d、e列が1なので、新たなエッジはc-dとc-eです。 d行はb、c列が1で、いずれも読み取り済みです。 e行はc、f列が1なので、新たなエッジはe-fです。 したがって、エッジはa-b、b-c、b-d、c-d、c-e、e-fの6本で、d-eのエッジはありません。 【選択肢別解説】 1：× 選択肢1（図のア）は、b-cの直線が無く、代わりにd-eの直線があります。 行列ではb-cは1、d-eは0なので一致しません。 2：× 選択肢2（図のイ）は、c-dの直線が無く、d-eの直線があります。 行列ではc-dは1、d-eは0なので一致しません。 3：○ 選択肢3（図のウ）は、a-b、b-c、c-d、e-fの直線と、上側の弧c-e、下側の弧b-dから成り、d-eの直線がありません。 6本のエッジが行列と完全に一致します。 4：× 選択肢4（図のエ）は、a-bからe-fまでの直線5本と弧2本の計7本で、行列に無いd-eのエッジを含んでいます。 【ポイント】 無向グラフの隣接行列は対称行列になります。 1の個数の合計を2で割るとエッジの本数になるので、図のエッジ数と照合すると素早く絞り込めます。