基本情報技術者試験「木とグラフ」の問題
頂点数が20個である1つの木(連結で閉路を持たないグラフ)の辺の本数はいくつか。
ア20本ちょうど
イ19本
ウ21本になる
エ40本である
正解
イ．19本
木は連結かつ閉路を持たないグラフで、頂点数nに対し辺数は常にn−1である。n=20なら20−1=19本となり正しい。
?選択肢ごとの解説
ア ×20本ちょうどは辺数を頂点数nと同じとした誤りで、辺が1本でも増えると閉路ができ木でなくなる。
イ ○木は連結かつ閉路を持たないグラフで、頂点数nに対し辺数は常にn−1である。n=20なら20−1=19本となり正しい。
ウ ×21本は頂点数+1とした誤りで、n−1という木の基本性質に反する。
エ ×40本は2nの値で、無向グラフの次数総和などと取り違えた誤りである。
✎くわしく
木の重要性質は『連結・閉路なし・辺数=n−1』の3条件が互いに関係する点。n頂点の連結グラフは辺数がn−1以上で、ちょうどn−1なら木になる。辺を1本加えると閉路が1つでき、辺を1本減らすと非連結になる。
✓本番での押さえどころ
試験のコツ
木の辺数は必ず『n−1』。根付き木でも自由木でもこの関係は変わらない点を押さえる。
覚え方
木は根以外の各頂点が親へ1本の枝を持つ=辺は頂点より1本少ない(n−1)、と親子関係で覚える。
よくある誤り
辺数をnやn+1と取り違える誤りが多い。木は『頂点より辺が1本少ない』と固定して覚える。
基礎理論の他の問題
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0090