問題

問3　隣接行列Aで表されるグラフはどれか。ここで、隣接行列とは、n個の節点から成るグラフの節点ViとVjを結ぶ枝が存在するときは第i行第j列と第j行第i列の要素が1となり、存在しないときは0となるn行n列の行列である。

解説と解答

　隣接行列Aの中で1の要素だけを(i, j)の形で書き出してみます。
(1, 2) (1, 3) (2, 1) (2, 4) (3, 1) (3, 4) (4, 2) (4, 3)
このうち、例えば(1, 2)と(2, 1)はV1とV2を結ぶ枝が存在することを表しています。

V1とV2、V1とV3、V2とV4、V3とV4が枝で結ばれた図、すなわちエが正解です。

城田 比佐子（しろた・ひさこ）
アイティ・アシストのインストラクター（プロスタッフ）。著書に『3週間完全マスター 基本情報技術者 2012年版』『3週間完全マスター 応用情報技術者 2012年版』などがある。