一个有向无环图(DAG)包含5个顶点和7条边。以下哪个描述是正确的?
答案解析
核心考点说明:本题考察有向无环图(DAG)的性质,包括入度、出度、拓扑排序等概念。DAG最重要的特性是没有环路。
解题思路分析:有向无环图的关键性质是没有环。入度为0的顶点称为源点,出度为0的顶点称为汇点。拓扑排序是针对DAG的排序,使得对于每条有向边 (u, v),顶点 u 在排序中出现在顶点 v 的前面。
选项分析:
A. 该图中每个顶点的入度和出度都小于等于2:错误。题目没有说明入度和出度的限制,顶点的入度和出度可以是大于2的。
B. 该图中至少存在一个入度为0的顶点,同时也至少存在一个出度为0的顶点:正确。在有向无环图中,至少存在一个入度为0的顶点(源点),也至少存在一个出度为0的顶点(汇点)。如果不存在源点,说明存在环路;如果不存在汇点,说明存在环路。
C. 该图中存在环路:错误。题目已经说明了该图是DAG,DAG的定义就是没有环路。
D. 该图的拓扑排序是唯一的:错误。DAG的拓扑排序可能存在多个,如果DAG的结构不是线性的,拓扑排序通常是不唯一的。
易错点提醒:注意DAG的定义,理解入度和出度的概念,以及拓扑排序的特性。
正确答案的关键依据:有向无环图必然存在入度为0的顶点和出度为0的顶点。
正确答案:B