平成29年度秋期応用情報技術者問6

テクノロジ系

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

図の内容（文字）

正解と解説

正解イ

木は閉路のない連結グラフで、ノード数5なら辺は4本です。行列の1が8個（辺4本）で全ノードがつながるのはイだけです。

木は、すべてのノードがつながっていて閉路（ループ）がないグラフです。n個のノードの木は、辺がちょうどn−1本になります。隣接行列は対称なので、1の個数の半分が辺の数です。イの辺は1-2、1-5、2-3、2-4の4本です。ノード1〜5がすべてつながり、閉路もないので木です。

ア：辺は1-2、1-5、2-3、3-4、4-5の5本です。1-2-3-4-5-1の閉路ができるので木ではありません。

ウ：辺は1-2、1-4、2-3、3-4、3-5の5本です。1-2-3-4-1の閉路ができるので木ではありません。

エ：辺は1-2、1-3、2-3、3-4、3-5、4-5の6本です。1-2-3と3-4-5の閉路ができるので木ではありません。

出典：平成29年度秋期応用情報技術者試験問6

全年度から出題。10問で実力を判定します。登録不要。

出典：平成29年度秋期応用情報技術者試験問6（独立行政法人情報処理推進機構）

解説と用語ページは生成 AI が書き、別の生成 AI が確かめています。作り方