問題 No.3411
基本情報技術者試験におけるグラフ理論の用語や性質に関して、不適切なものはどれか。
【正解の解説】
閉路を持たない連結な無向グラフは、頂点数がV個のとき辺の数が必ずV個である。
木構造をイメージしてください。3人の友達をロープで輪を作らずに全員がつなぐ場合、必要なロープの数は必ず2本（3-1）になります。輪っか（閉路）を作ってしまうと枝の数が頂点数と同じになってしまうため、この数学的なルールに違反してしまいます。
スポンサーリンク
【その他の選択肢の解説】
閉路を持たない連結な無向グラフは、頂点数がV個のとき辺の数が必ずV-1個である。
初学者が最も勘違いしやすい「木」というグラフの基本ルールです。頂点同士を一本道で繋いでいくと、最後のゴールにたどり着くための辺の数は必ず「頂点数マイナス1」になります。例えば電柱が3本なら電線は2本で繋がるのと同じイメージです。
すべての頂点の次数が等しい無向グラフにおいては、頂点数の総和と辺の数の総和が常に等しくなる。
1本の辺は必ず両端の2つの頂点を結んでいます。そのため、すべての頂点から出ている次数を足し合わせると、辺の数のちょうど2倍になります。ここを混同して「頂点数と辺数が等しい」と思い込むのは試験でよく狙われる典型的なひっかけパターンです。
すべての頂点間に直接の辺が存在する完全グラフでは、頂点数がV個のとき辺の数がV(V-1)個になる。
総当り戦の試合数や全員が握手する回数を想像してください。V人が自分以外の(V-1)人と線で結ばれるため、一見するとV(V-1)本ですが、AさんとBさんの線、BさんとAさんの線は同じ1本を指すため、最後に必ず2で割る必要があります。