ノード1〜5をもつグラフを隣接行列で表したもののうち、木となるものはどれか。ここで、隣接行列のi行j列目の成分は、ノードiとノードjを結ぶエッジがある場合は1、ない場合は0とする。

選択肢

• アア：5×5の隣接行列 [[0,1,0,0,1],[1,0,1,0,0],[0,1,0,1,0],[0,0,1,0,1],[1,0,0,1,0]]
• イイ：5×5の隣接行列 [[0,1,0,0,1],[1,0,1,1,0],[0,1,0,0,0],[0,1,0,0,0],[1,0,0,0,0]]
• ウウ：5×5の隣接行列 [[0,1,0,1,0],[1,0,1,0,0],[0,1,0,1,1],[1,0,1,0,0],[0,0,1,0,0]]
• エエ：5×5の隣接行列 [[0,1,1,0,0],[1,0,1,0,0],[1,1,0,1,1],[0,0,1,0,1],[0,0,1,1,0]]

正解と解説

正解：イ イ：5×5の隣接行列 [[0,1,0,0,1],[1,0,1,1,0],[0,1,0,0,0],[0,1,0,0,0],[1,0,0,0,0]]

nノードのグラフが木であるためには、連結であり、かつ閉路をもたず、辺の本数がn-1本である必要がある。ノードが5個なので辺は4本でなければならない。イは1-2、1-5、2-3、2-4の4本の辺で全ノードが連結され、閉路も無いので木となる。

選択肢ごとの解説

• ア辺が5本あり、1-2-3-4-5-1という閉路ができるので木ではない。
• イ正しい。辺が4本で連結かつ閉路が無い。
• ウ辺が5本あり閉路を含むので木ではない。
• エ辺が6本あり閉路を含むので木ではない。

同じ分野の他の問題

• 図の2分探索木に1と0の二つの要素を順に追加したAVL木として，適切なものはどれか。2025年度 春期 午前 問6
• A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データ…2016年度 春期 午前 問5
• 次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の…2024年度 秋期 午前 問5
• 各ノードがもつデータを出力する再帰処理f(ノードn)を定義した。この処理を、図の2分木の根(最上位のノード)から始めたと…2024年度 春期 午前 問6
• 双方向リストを三つの一次元配列elem[i]、next[i]、prev[i]の組で実現する。双方向リストが図の状態のとき…2023年度 秋期 午前 問5