平成29年度 秋期 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズムノード1～5をもつグラフを隣接行列で表したもののうち，木となるものはどれか。ここで，隣接行列のi行j列目の成分は，ノードiとノードjを結ぶエッジがある場合は1，ない場合は0とする。 （注：本サイトでは原問題の表を文字表記に変換しています）
出典：平成29年度 秋期 応用情報技術者試験 午前 問6
- ア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
- イ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
- ウ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
- エ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ノードの木は，連結でありながら閉路（サイクル）をもたず，辺の数がちょうどノード数－1（4本）になっている必要があります。イの行列が表す辺は1-2，1-5，2-3，2-4の4本で，全ノードが連結し閉路もないため木になります。他の選択肢は辺が5本以上あり閉路を含むため木にはなりません。
選択肢ごとの解説
- ア誤り。この行列は辺が1-2，1-5，2-3，3-4，4-5の5本あり，1-2-3-4-5-1という閉路を含むため木ではありません。
- イ正しい。この行列が表す辺は1-2，1-5，2-3，2-4の4本で，全てのノードが連結し閉路を含まないため木になります。
- ウ誤り。この行列は辺が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本あり，複数の閉路を含むため木ではありません。