我要招人

去企业版

首页 > 试题广场 >

n 个顶点，m 条边的全连通图，至少去掉几条边才能构成一棵树

[单选题]

n 个顶点，m 条边的全连通图，至少去掉几条边才能构成一棵树？

```
m-n
```
```
m-n+1
```
```
m-n-1
```
```
m-2n
```

推荐

忆梦＆....

n个顶点的树一定有n-1条边，所以需要去掉m-(n-1)=m-n+1条边

编辑于 2015-02-02 21:42:41 回复(3)

沫。

全连通图若有n个结点，则边数是n（n-1）/2。而若要构成树，则它的边数是n-1。所以本题是去掉m-(n-1)条边即可

发表于 2016-08-09 08:57:51 回复(0)

dragonhaw

两种方法：

1. 因为是全连通图，其实m=n(n - 1) / 2，举个例子，4个顶点6条边，要得到(n - 1)即3即构成一棵树，代入答案中得B。

2. 要得到(n - 1)才能构成一棵树，m - x = n - 1，解得x = m - n + 1，选B。

发表于 2017-05-04 22:52:21 回复(0)

幽荧

总共m条件，n个顶点最少需要n-1条边来连接。两者相减，即可得出正确答案！

发表于 2021-08-17 12:36:45 回复(0)

道小理

一个有n个顶点的全连通图至少要去掉m-n+1条边才能构成一棵树。这是因为一棵树有n个顶点和n-1条边，而全连通图有m条边，如果想得到一棵树就需要去掉m-(n-1)=m-n+1条边。

发表于 2023-04-08 16:48:43 回复(0)

#include

若有n个结点，则全连通图边数是n*(n-1)/2。

而若要构成树，则它的边数是n-1。

所以本题是去掉m-(n-1)条边即可

编辑于 2019-04-03 20:20:30 回复(0)

Forrest_Lin

对于有向或无向图，n个顶点要构成一棵树，需要（n-1）条边。对于有向图，需要删除的是是任意顶点多于1个入度的弧，使得某个顶点的入度为0,而其余所有顶点的入度为1,即一棵树的判定定理。

发表于 2018-04-25 16:21:39 回复(0)

邓文达

B 树的边数比节点数少1。要将图变成树，应该只有n-1条边。因此需要删除m-(n-1)条边，即m-n+1条边

发表于 2018-01-25 22:05:37 回复(0)

黏黏糖

若能构成一棵树，则n个顶点的树中必然有n-1条边。因此去掉的边数为m-(n-1)=m-n+1

发表于 2017-05-24 15:17:38 回复(0)

williamliums

直接用3个结点2条边的二叉树验证来的快

发表于 2016-08-25 17:14:58 回复(0)

DJL箫氏

感觉这样题可以直接举个例子验证每个选项

发表于 2016-08-16 11:37:27 回复(0)

Ryan.H

全连通图节点n (n-1)/2条边连通图至少n-1条边故减去m -n+1条边可形成连通图

发表于 2016-05-24 08:43:36 回复(0)

huixieqingchun

n个结点的树，一定有n-1条边，

发表于 2016-05-07 21:32:59 回复(0)

i＇mLT

发表于 2015-04-24 23:16:29 回复(0)

提交观点

问题信息

树

上传者：小海豹

难度：

14条回答 356收藏 26673浏览

n 个顶点，m 条边的全连通图，至少去掉几条边才能构成一棵树

问题信息

热门推荐

相关试题