【对于一个有n个顶点和e条边的连通图,其生成树中顶点数和边数-查字典问答网

来自丁学伟的问题

　　【对于一个有n个顶点和e条边的连通图,其生成树中顶点数和边数分别为请将过程描述下】

　　对于一个有n个顶点和e条边的连通图,其生成树中顶点数和边数分别为

　　请将过程描述下

1回答

2020-10-1704:22

我要回答

提示：回答问题需要登录哦！

提交

胡玉娥

　　生成树中顶点数和边数分别为n,n-1.

　　这个问题十分简单,上面两位已给出了正确答案,如果你还不满意,我给你再解释一下,生成树首先是一个生成子图,其次它是一个树,所谓生成子图是包含图中所有顶点的子图,原图有n个顶点,故生成树也应有n个顶点,关于树的定义很多,通常定义为没有回路的连通图,或者定义为最小连通图,(即删去任意一条边就会不连通的连通图),n个顶点的最小连通图至少有n-1条边,如果少于n-1条边一定不会是连通的,如两个顶点的图必有1条边才能确保它连通,3个顶点的图必有2条边才能确保它连通,等等,又n个顶点的最小连通图至多有n-1条边,否则一定会有回路,如果有了回路,删去回路中的任意一条边仍会连通,这样它就不是最小连通图了,故生成树不多不少恰有n-1条边.

　　上面给了你直观的解释,严格证明图论书中均有,希你看看.