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

$N$ 个顶点的有向完全图（不带自环）有 $N \times (N - 1)/2$ 条边。

这题考有向完全图边数公式。别被‘完全图’带偏，直接想：N个点，每对点连两条反向边，总边数就是N×(N−1)。

很多人一看到‘完全图’就条件反射套无向图公式n(n−1)/2，或者把‘有向完全图’脑补成竞赛图（单向边），结果选错。其实‘有向完全图’定义就是任意两点间都有两条方向相反的有向边，边数自然翻倍成n(n−1)。

【考点】图论基础｜有向完全图定义｜边数公式计算

这道题考查的是对‘有向完全图’这一术语的准确理解，以及如何根据定义计算其边数。命题人故意用‘有向完全图’这个说法，就是想测试你：是不是真的知道它和无向完全图的区别，而不是只会背公式。

先说概念：在图论里，‘完全图’通常指无向完全图，即任意两个不同顶点之间都有一条边相连，边数为n(n−1)/2。而‘有向完全图’的定义是：任意两个不同顶点之间都有两条方向相反的有向边（即双向边）。题目还特别注明‘不带自环’，这其实是冗余信息——因为完全图本来就不允许自环，但命题人加上它，可能是为了强调‘只考虑不同顶点对’，也可能是想迷惑你，让你以为它在暗示某种特殊的计数方式。

接下来看命题视角：为什么选B？因为题干给出的边数是n(n−1)/2，这恰恰是无向完全图的边数。如果是有向完全图，每对点贡献两条边，总边数应该是n(n−1)。所以A选项错误，B选项正确。

思考过程可以这样展开：拿到题先确认图类型——有向还是无向？有向的话再看是否‘完全’：每对点是否双向连边？如果是，边数就是n(n−1)。如果不是，而是单向（竞赛图），边数才是n(n−1)/2。这里的关键是‘有向完全图’的‘完全’二字，意味着双向，所以边数翻倍。

避坑提醒：最容易错的就是把‘有向完全图’当成‘竞赛图’，或者看到公式n(n−1)/2就以为是对的。其实竞赛图也叫‘有向完全图’吗？不，竞赛图是单向的，严格来说不叫‘有向完全图’。命题人就是利用这种术语混淆来挖坑。

考频与趋势：从题库数据看，‘图的基本概念’在历年考试中非常高频，2023年考了36题，2024年61题，2025年58题，2026年71题，呈逐年上升趋势。其中GESP八级就考了85题，说明这类概念辨析题在八级考试中占比很高。‘图形结构’考点也考了213题，覆盖所有级别，但‘图的基本概念’更侧重术语定义，是八级重点。

预测：基于近年趋势，未来GESP八级仍会高频考查图论基础术语辨析，尤其是‘有向完全图’‘无向完全图’‘竞赛图’‘简单图’等概念的区别。命题人可能会继续用类似‘不带自环’‘有向’等细节来制造陷阱，或者结合算法题（如最短路径、拓扑排序）来考察对图结构的理解。因此，复习时要特别注意术语的精确定义，不能只看公式。

综上，这道题答案选B，因为N个顶点的有向完全图边数是n(n−1)，而不是n(n−1)/2。