🏷️ 知识点：出度

在含有 n 个顶点的简单有向图中，单个顶点的总度（入度与出度之和）最大为（ ）。

A. n B. n−1 C. 2n D. 2n−2

[tag_link]

正确答案：D

结论

单个顶点的总度最大为 2n−2。

推导

简单有向图没有自环和重边。对任一顶点，最多向其余 n−1 个顶点各发出一条边，出度至多 n−1；其余顶点也最多各有一条边指向它，入度至多 n−1。因此总度上界为 (n−1)+(n−1)=2n−2，且可同时达到。

易错点

不要只计算出度 n−1；题目问的是入度加出度。也不要把无向图的度数上界直接套到有向图。