在一个有向图中,如果存在一个顶点,它到其他所有顶点都有路径,但这个图不是强连通的,那么这个图至少有多少个顶点?
答案解析
核心考点说明:本题考察的是图论中的连通性概念,特别是强连通图和有向图的基本性质。
解题思路分析:首先,理解强连通图的定义,即图中任意两个顶点之间都存在双向路径。题目中提到的图不是强连通的,但存在一个顶点到其他所有顶点都有路径,这意味着图中至少存在一个顶点,它到其他所有顶点都是可达的,但反过来不一定成立。
每个选项的详细分析:
- A. 2:两个顶点的有向图如果存在一个顶点到另一个顶点的路径,那么这个图就是强连通的,与题目条件矛盾。
- B. 3:三个顶点的有向图可以构造出一个顶点到其他两个顶点都有路径,但整个图不是强连通的情况,符合题目条件。
- C. 4:虽然四个顶点的图也能满足条件,但不是最小的。
- D. 5:同理,五个顶点的图也能满足条件,但不是最小的。
易错点提醒:容易忽略题目中‘至少’这个条件,而选择不是最小顶点数的选项。
正确答案的关键依据:三个顶点的有向图是满足条件的最小图。
正确答案:B