GESP 八级 · GESP 202403 C++ 八级 第 19 题

$N$ 个顶点的无向完全图有 $N \times (N - 1)$ 条边。

图的存储方式：邻接矩阵（O(n²)空间，适合稠密图）、邻接表（O(n+m)空间，适合稀疏图）。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】组合数学｜图论基础｜握手定理

考纲定位八级考查图论概念辨析，命题人用错误公式卡住死记硬背者。多数考生看到"完全图"就条件反射输出 N(N-1)/2，反而被题干故意给出的 N(N-1) 诱入陷阱。

解题思维无向完全图每对顶点间恰有一条边，N 个顶点两两组合数为 C(N,2)=N×(N-1)/2。N×(N-1) 是重复计算了每条边两次（u→v 与 v→u），因此题干公式错误选 B。这类组合计数题通法：先想"每对元素贡献几条边"，再乘以组合数 C(N,2)，最后根据有无向/是否自环调整。

陷阱拆解题干公式 N(N-1) 恰好是有向完全图的边数，命题人故意偷换"有向/无向"概念。若你只背结论不推本质的，看到 N(N-1) 会误判为正确。更阴险的是 N×(N-1) 与正确答案 N×(N-1)/2 仅差因子 1/2，这种"差个系数"的选项专门筛掉计算粗心的人。

反命题思维若改题问"有 N 个顶点的有向完全图有多少条边？"答案就是 N×(N-1)，这提示你：命题人可能在下一题考有向图。刷这类题时先问自己"有无向二字"，再决定公式要不要除以 2。