有29条边的无向连通图，至少有（）个顶点，至多有（）个顶点。

[问答题]

天尊墨宇

至少有9个顶点，至多有30个顶点

发表于 2020-08-09 11:12:55 回复(0)

今夕kpole

在无重边，无自环的前提下，最少有9个点，因为 8 个点两两连边会有 28 条边，所以最少必须要9个点，最多可以是30个点，比如一棵树

发表于 2020-06-01 20:30:34 回复(0)

-字节跳动校招-

至少应该是9个顶点吧((n-1)*(n-2)/2+1)(n是顶点)，最多应该是29个顶点吧(一个环的情况)，不知道对不对

发表于 2020-06-01 15:40:43 回复(0)

DosonMu

<p>用邻接矩阵M解决，M上1的分布即刻为边，矩阵的边长为节点数。该问题转化为矩阵的最短边长和最长边长。在必须有29个边的条件下（不含有环），最短边长:m(m-1)/2=29,m=9,最长为29</p>

发表于 2020-06-01 08:20:46 回复(0)

提交观点

问题信息

图

上传者：城市里的养猫者

难度：

4条回答 1收藏 4855浏览

扫一扫，把题目装进口袋