問題
ノード 1〜5 をもつグラフを隣接行列で表したもののうち、木となるものはどれか。ここで、隣接行列の i 行 j 列の成分は、ノード i とノード j を結ぶエッジがある場合は 1、ない場合は 0 とする。
選択肢
- 1（ア）の隣接行列
- 2（イ）の隣接行列
- 3（ウ）の隣接行列
- 4（エ）の隣接行列
正解
2. （イ）の隣接行列
詳しい解説を見る解説を閉じる
解説
ノード数 n の連結グラフが木であるためには、エッジ数がちょうど n−1 本で、かつ閉路（サイクル）をもたないことが必要十分条件である。ノード 5 個の木はエッジが 4 本で、隣接行列の上三角部分（または下三角部分）の 1 の個数が 4 個になり、サイクルを含まない。これらの条件を満たすのはイの隣接行列である。よってイが正解。（出典: 平成29年度 秋期 応用情報技術者試験 午前 問6）
一問一答
全400問を繰り返し学習