首页 > 试题广场 >

证明：具有n个顶点的无向图最多有n×(n-1)2条边。

[问答题]

证明：具有n个顶点的无向图最多有n×(n-1)/2条边。

添加回答
雅尔达winniebaby92头像 雅尔达winniebaby92
n个顶点的无向图，每个顶点都可以与另外n-1个顶点相连，构成n(n-1)条边，但每条边都被算了两次，故要除以2，即n(n-1)/2
发表于 2018-03-02 16:19:43 回复(0)
牛客4414733号头像 牛客4414733号
当任意两结点中都有一条边时，边数最多，则
1+2+3+....+(n-1)=(n-1+1)*(n-1)/2=n*(n-1)/2
发表于 2017-12-03 20:56:39 回复(0)
提交观点

问题信息

图
上传者：城市里的养猫者
难度：
2条回答 3103浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号