对于有n个顶点的无向图,所有生成树中都有且仅有的边数是()
A、
n+1条
B、
n-1条
C、
n条
D、
2n条
【正确答案】:B
【题目解析】:
一个连通图的生成树,是含有该连通图的全部顶点的一个极小连通子图。若连通图G的顶点个数为n,则G的生成树的边数为n-1。如果边数大于n-1,则一定有环。
即对于有n个顶点的无向图,所有生成树中都有且仅有n-1条边。故选B。
对于有n个顶点的无向图,所有生成树中都有且仅有的边数是()
对于有n个顶点的无向图,所有生成树中都有且仅有的边数是()
n+1条
n-1条
n条
2n条
一个连通图的生成树,是含有该连通图的全部顶点的一个极小连通子图。若连通图G的顶点个数为n,则G的生成树的边数为n-1。如果边数大于n-1,则一定有环。
即对于有n个顶点的无向图,所有生成树中都有且仅有n-1条边。故选B。