单选题
一个连通图的生成树是包含图中所有顶点的一个______子图。n(n>1)个顶点的强连通图中至少含有______条有向边。
A、
极小
B、
连通
C、
极小连通
D、
无环
【正确答案】
C
【答案解析】
A、
n-1
B、
.n
C、
n(n-1)/2
D、
n(n-1)
【正确答案】
A
【答案解析】
[解析] 一个连通图的生成树是包含图中所有顶点的一个极小连通子图,用n-1条边连通n个顶点。n(n>1)个顶点的强连通图中至少含有n条有向边。如果这n条边形成一个有向环,就能强连通。
提交答案
关闭