修了試験 2022-07-24実施分 基本情報技術者試験 問2

解説

正解は4です。 隣接行列は、節点ViとVjが枝で結ばれていれば第i行第j列が1、結ばれていなければ0になる行列です。 行列Aの1の位置を読み取り、同じ枝をもつグラフを探します。 第1行は（0,1,1,0）なので、V1はV2とV3に結ばれています。 第2行は（1,0,0,1）なので、V2はV1とV4に結ばれています。 第3行は（1,0,0,1）なので、V3はV1とV4に結ばれています。 第4行は（0,1,1,0）なので、V4はV2とV3に結ばれています。 つまり枝は「V1とV2」「V1とV3」「V2とV4」「V3とV4」の4本です。 V1とV4、V2とV3は結ばれていません。 【選択肢別解説】 1：× 選択肢1（図のア）は、V1とV4、V4とV2、V4とV3、V2とV3を結んでいます。 行列では0であるV1とV4、V2とV3の枝があるので一致しません。 2：× 選択肢2（図のイ）は、4つの節点のすべての組を結んだ6本の枝をもちます。 行列の枝は4本だけなので、V1とV4、V2とV3の枝が余分です。 3：× 選択肢3（図のウ）は、V1とV2、V1とV3、V1とV4、V2とV3を結んでいます。 V4はV1だけと結ばれていますが、行列ではV4はV2とV3に結ばれるので一致しません。 4：○ 選択肢4（図のエ）は、V1とV2、V1とV3、V4とV2、V4とV3を結んでいます。 V1とV4、V2とV3は結ばれておらず、行列Aの1と0の位置にすべて一致します。 【ポイント】 無向グラフの隣接行列は、対角線を挟んで対称になります。 各行の1の個数は、その節点につながる枝の本数（次数）を表します。 本問はどの行も1が2個なので、全節点の次数が2の図を探せば速く解けます。