在具有n个顶点的无向完全图中删去()条边才可能得到一棵树?
发布网友
发布时间：2022-05-10 11:52
共3个回答
热心网友
时间：2023-10-09 03:48
D。
因为每条边可以看作是两个顶点的集合，由于是完全图，所以相当于找n个顶点中取两个点的取法，一共是C(n,2)=n(n-1)/2种。
n个顶点的树一定有n-1条边（证明可以看任何一本图论书），所以需要去掉m-(n-1)=m-n+1条边。
无向图的最多边是无向完全图：包含n(n-1)/2条边。因为一条边关联两个结点，有向完全图的才有n(n-1)条弧。而无向图变联通至少边数：n-1。有向图变连通图至少需要边数：n。
扩展资料：
无向图G=<V,E>,其中：
V是非空集合，称为顶点集。
E是V中元素构成的无序二元组的集合，称为边集。
直观来说，若一个图中每条边都是无方向的，则称为无向图。
无向边的表示
无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
参考资料来源：百度百科-无向图
热心网友
时间：2023-10-09 03:48
在具有n个顶点的无向完全图中删去[ (n-1)(n-2) /2]条边才可能得到一棵树。
具有n个顶点的无向完全图*有n (n-1) /2条边，n个顶点的树应用n-1条边，于是，删去的边数为：n (n-1) /2- ( n-1 ) =(n-1)(n-2) /2。
扩展资料
无向边的表示：无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
例：无序对(vi，vj)和(vj，vi)表示同一条边。
边没有方向的图称为无向图。无向图G=<V，E>，其中：
1、V是非空集合，称为顶点集。
2、E是V中元素构成的无序二元组的集合，称为边集。
热心网友
时间：2023-10-09 03:48
