对于一个有n个顶点和e条边的连通图,其生成树中顶点数和边数分别为
请将过程描述下
人气:225 ℃ 时间:2019-11-10 20:15:12
解答
生成树中顶点数和边数分别为n,n-1.
这个问题十分简单,上面两位已给出了正确答案,如果你还不满意,我给你再解释一下,生成树首先是一个生成子图,其次它是一个树,所谓生成子图是包含图中所有顶点的子图,原图有n个顶点,故生成树也应有n个顶点,关于树的定义很多,通常定义为没有回路的连通图,或者定义为最小连通图,(即删去任意一条边就会不连通的连通图),n个顶点的最小连通图至少有n-1条边,如果少于n-1条边一定不会是连通的,如两个顶点的图必有1条边才能确保它连通,3个顶点的图必有2条边才能确保它连通,等等,又n个顶点的最小连通图至多有n-1条边,否则一定会有回路,如果有了回路,删去回路中的任意一条边仍会连通,这样它就不是最小连通图了,故生成树不多不少恰有n-1条边.
上面给了你直观的解释,严格证明图论书中均有,希你看看.
推荐
猜你喜欢
- 已知abcd是有理数,a减b的绝对值小于等于9,c减d的绝对值小于等于16,且a减b减c加d的绝对值等于25,求b减a的绝对值减去d减c的绝对值的值
- 写比喻句
- 已知等差数列{an}中,公差d=1,且S99=99,求a2+a5+a8+……a95+a98的值
- Miss you but I can't tell you my heart good unco翻译中文
- 如果两组数据x1,x2,…,xn和y1,y2,…yn的平均数分别为x拔,y拔,求一组新数据:ax1+by1,ax2+by2,…,axn+byn的平均数.
- 成语填空:万()千(),要四个这样的成语.
- 甲乙两车从AB两点同时出发,相向而行 在距离中点20千米处相遇,此时甲比乙多行20%,则AB两地相距多少千米
- 九分之五的分数单位是(),再添上几个这样的单位就是最小的质数