以下说法正确的是( )。
A. 连通分量是无向图中的极小连通子图
B. 强连通分量是有向图中的极大强连通子图
C. 在一个有向图的拓扑序列中若顶点a在顶点b之前,则图中必有一条弧<a,b>
D. 对有向图G,如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点,则该图一定是完全图
无向图G的极大连通子图称为G的连通分量
D错,因为如果有向图构成双向有向环时,则从任一顶点出发均能访问到每个顶点,但该图却非完全图。
弧:指的是有向图里面的边,他是有明确方向的。如果是无向图的边,直接叫做“边”。比如有向图的 v1 结点到 v2 结点的弧可能是:<v1, v2>;
极大连通子图:无向图的联通分量; 极小连通子图:树。
b
B
极大连通子图是讨论连通分量的,极小连通子图是讨论生成树的。
强连通图:在有向图中,若对于每一对顶点Vi和Vj,都存在一条从Vi到Vj和从Vj到Vi的路径,则称此图为强连通图。
用户登录可进行刷题及查看答案
登录后提交答案