GESP 七级 · GESP 202506 C++ 七级 第 8 题

一个连通的简单有向图，共有 28 条边，则该图至少有（ ）个顶点。

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

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

【考点】有向图边数上限｜连通图最小顶点数

1. 考纲定位：本题考查图论中"n个顶点的简单有向图最大边数为n(n-1)"这一核心结论，对应GESP七级图论模块。命题人刻意用"连通"一词卡住考生——多数人会无脑套用无向图的n-1边，却忽略有向图每条边可独立连接两顶点，上限是n(n-1)。

2. 解题思维：看到"连通有向图+28条边"先想"最大边数公式"，代入n(n-1)≥28试算：n=6时30≥28，n=5时20<28，故最小顶点数6。关键观察是"简单有向图无重边/自环"，因此每个顶点至多n-1条出边，总边数上限n(n-1)。

3. 陷阱拆解：选项A（5）源于误用无向图公式；C、D则因未区分"连通"在有向图中仍允许最大边数n(n-1)。最阴险细节是"连通"二字——考生易联想无向连通需n-1边，但有向连通（弱连通）同样可达n(n-1)边，命题人用此混淆概念。若只背"连通图边数≈顶点数"必掉坑。

4. 反命题思维：若改为"无向图28条边至少多少顶点"，答案变8（n(n-1)/2≥28）。提醒：刷到"图+边数+顶点"类题，先确认有向/无向、连通/强连通，再套公式。