基本情報技術者試験「グラフ理論」の問題
ある無向グラフの各頂点の次数が 2,3,3,4,4 であった。このグラフの辺の本数はいくつか。
ア次数の総和と同じ16本になる
イ5本
ウ7本ある
エ8本である
正解
エ．8本である
握手補題により『次数の総和=辺数×2』が成り立つ。次数の総和は2+3+3+4+4=16で、辺数はその半分の16÷2=8本となり正しい。
?選択肢ごとの解説
ア ×16本は次数の総和そのままの値で、辺数に変換するため2で割る手順を忘れた典型的な誤りである。
イ ×5本は頂点数(5個)を辺数と取り違えた誤りで、次数の情報を使っていない。
ウ ×7本は次数の総和16から誤った引き算をするなど、握手補題の÷2を適用できていない値である。
エ ○握手補題により『次数の総和=辺数×2』が成り立つ。次数の総和は2+3+3+4+4=16で、辺数はその半分の16÷2=8本となり正しい。
✎くわしく
握手補題は『各辺が両端の2頂点に1ずつ次数を寄与する』ことから導かれる。よって次数の総和は必ず偶数で、辺数はその半分になる。次数の総和が奇数のグラフは存在しないという帰結も重要である。
✓本番での押さえどころ
試験のコツ
無向グラフは『次数の総和÷2=辺数』を機械的に適用する。総和が奇数になったら数え間違いと判断できる。
覚え方
握手=2人で1回。各辺は両端に1ずつ握手するので、握手回数(次数和)の半分が辺数、と覚える。
よくある誤り
次数の総和をそのまま辺数とする(÷2忘れ)、または頂点数と辺数を混同する誤りが多い。
基礎理論の他の問題
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0088