n个顶点的连通图的生成树有( )条边。
A. n
B. n-1
C. n+1
D. 不确定
N诺智能批改可自动批改答案并给出反馈,每次使用将消耗 1个诺币
您当前的诺币数量: 个
N诺正在智能批改,预计需要30秒,请稍候...
生成树首先是一个连通图的子图,它包含图中的所有顶点。
○ 生成树是一个无回路(即没有环)的连通图。
○ 对于一个具有n个顶点的连通图,如果要构建一个无回路的连通子图(也就是生成树),我们可以从一个顶点开始,逐步添加边来连接其他顶点。
○ 当我们从第一个顶点开始连接第二个顶点时,需要1条边;连接第三个顶点时,因为要保证无回路且连通,所以再添加1条边即可,此时共2条边连接了3个顶点;连接第四个顶点时,同样添加1条边,此时3条边连接了4个顶点。
○ 以此类推,每连接一个新的顶点,就需要添加1条边。当连接完n个顶点时,总共添加的边数比顶点数少1。
B
登录后提交答案