🏷️ 知识点：有向图

共 2 道相关题目

课后题年第 4 题数据结构选择题

以下关于图的叙述中，正确的是（）。

A. 强连通有向图的任何顶点到其他所有顶点都有弧 B. 图的任意顶点的入度等于出度 C. 有向完全图一定是强连通有向图 D. 有向图的边集的子集和顶点集的子集都构成原有向图的子图

[tag_link]

正确答案：C

C 正确。

有向完全图对任意不同顶点都含相应方向的弧，因此任意顶点可达其他顶点，必强连通。A 把“存在路径”误作“直接有弧”；B 无一般性；D 子图中的边端点必须属于所选顶点集。

强连通要求路径可达，不要求每对顶点间都有一条直接弧；完全图才提供直接弧。

课后题年第 8 题数据结构选择题

在含有 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；题目问的是入度加出度。也不要把无向图的度数上界直接套到有向图。