GESP 七级 · GESP 202403 C++ 七级 第 9 题

一个简单有向图有 $10$ 个结点、$30$ 条边。再增加多少条边可以成为完全图。（ ）

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

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

【考点】有向完全图边数公式｜简单图定义

1. 🎯 考纲定位（考点定位）

GESP 七级图论模块核心考点。命题人卡住的是"有向图完全图边数易混无向图"这一普遍认知陷阱——大量学生背了 n(n-1)/2 的无向公式，见到有向图条件反射用错，或者把顶点数当边数直接乘。本题用 10 个结点、30 条边的具体数据故意制造计算空间，就是测试你是否真正理解完全图边数公式。