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

来源：学生作业帮编辑：神马作文网作业帮分类：数学作业时间：2024/11/18 18:53:50

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

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

(72) n个顶点的强连通图的边数至少有______.(C) 对于一个非连通无向图,共有28条边,则该图至少有多少个顶点? 若G是一个具有36条边的非连通无向图（没有自回路和多重边）,则G至少有____个顶点? 运筹学判断题：在所有顶点数相同的连通图中,树的边数最少设无向连通图G有n个顶点,证明G至少有（n-1）条边. 对于一个具有N个顶点E条边的无向图的邻接表的表示,则表头向量大小为多少?邻接表的顶点总数为多少?（请给出详细的分析过程）设一个包含N个顶点、E条边的简单有向图采用邻接矩阵存储结构（矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有如果一个平面图有20个顶点和11个区域.那么利用顶点数,边数,区域数之间的关系,这个平面图有几条边? 图论证明,图G带v个顶点,e条边的连通平面图简单图,其中v大于等于3且圈的长度为L. 三角形测试题有三个多边形,他们的边数分别为m、n、k,若过m边形的一个顶点恰好有6条对角线,n边形恰好有n条对角线,k边对于n棱柱,面的个数,顶点个数,棱的条数分别是多少? 设一个无向图G=(V,E)有n个顶点n+1条边,证明G中至少有一个顶点的度数大于或等于3.