如果具有n个顶点的图是一个环，则它有( )棵生成树。

admin2018-07-17 10

问题如果具有n个顶点的图是一个环，则它有( )棵生成树。

选项 A、n²
B、n
C、n一1
D、1

答案B

解析考查图的生成树。n个顶点的生成树是具有n—1条边的极小连通子图，n个顶点构成的环具有n条边，去掉任一条边后剩下的图依然是连通的。因为n个顶点构成的环共有n条边，去掉其中任意一条便是一棵生成树，共有n种情况，所以可以有n棵不同的生成树(如，以n=3为例读者自行分析)。

转载请注明原文地址:https://kaotiyun.com/show/hyRi777K

计算机408

相关试题推荐

随机试题

最新回复(0)