基本情報技術者試験「グラフ理論」の問題
6個の頂点すべてが互いに1本ずつ辺で結ばれた無向の完全グラフがある。辺の総数はいくつか。
ア15本である
イ30本
ウ36本ある
エ全部で12本
正解
ア．15本である
完全グラフは異なる2頂点の組すべてに1本の辺がある。辺数は2頂点の選び方6C2=6×5/2=15本となり正しい。
?選択肢ごとの解説
ア ○完全グラフは異なる2頂点の組すべてに1本の辺がある。辺数は2頂点の選び方6C2=6×5/2=15本となり正しい。
イ ×30本はn(n−1)=6×5の値で、無向グラフなのに同じ辺を両方向で二重に数えた(2で割り忘れた)誤りである。
ウ ×36本はn^2=6×6であり、自分自身への辺や重複を含めて数えた誤りである。完全グラフに自己ループはない。
エ ×全部で12本は2nなど辺数の公式と無関係な計算による値で、組合せの考え方を使っていない。
✎くわしく
完全グラフの辺数は『異なる2頂点の組合せ数』nC2=n(n−1)/2に等しい。各頂点の次数はn−1で、次数の総和n(n−1)を握手補題で2で割っても同じ式が得られる。組合せと握手補題の両方で導けることが核心である。
✓本番での押さえどころ
試験のコツ
完全グラフの辺数は『nC2=n(n−1)/2』と暗記する。無向なら必ず2で割る点を忘れない。
覚え方
全員が全員と1回ずつ握手する人数nの握手回数=nC2、と握手会のイメージで覚える。
よくある誤り
無向グラフで2で割り忘れてn(n−1)とする、またはn^2と数える誤りが頻出する。
基礎理論の他の問題
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0089