Question

连通图G的顶点数位N，则G的生成树的边数是多少

Answer 1

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