首页 > 试题广场 >

假设一个无向图中包含 12 个顶点，其中 5 个顶点有 5

[单选题]

假设一个无向图中包含 12 个顶点，其中 5 个顶点有 5 个度，7 个顶点有 7 个度，那么这个图有几条边？（）

查看正确选项

绅蓝

一条边带来两个度，（7*7+5*5）/2=37

发表于 2019-03-26 10:06:07 回复(10)

牛客、芒果熊

一条边带来两个度，（7*7+5*5）/2=37

发表于 2022-11-14 15:22:53 回复(0)

simon_free

首先，我们需要了解什么是度。在无向图中，每个顶点的度是与该顶点相邻的所有其他顶点的数量。

根据题目给定的信息，我们有5个顶点都是5度，这意味着每个这样的顶点都有5个邻居。另外，我们还有7个顶点都是7度，意味着每个这样的顶点都有7个邻居。

对于第一个情况，一个顶点与它的5个邻居的关系可以看作是有5条边，但是这些边被计数了两次（因为它们连接两个不同的顶点）。所以我们需要除以2来消除重复。所以，这些5度顶点一共贡献了5 * 5 / 2 = 12.5 条边。

同样的，对于7度的顶点，它们一共贡献了7 * 7 / 2 = 24.5 条边。

现在我们知道所有的顶点共贡献了12.5 + 24.5 = 37条边。

所以，这个无向图有37条边。

发表于 2023-11-16 13:16:36 回复(0)

牛客915976740号

那个式子和顶点n没有任何关系哈

发表于 2022-11-12 16:35:33 回复(0)

ddssddgg

题目意思会错了，以为五个顶点只有五个度，这怎么可能

发表于 2022-04-25 20:45:23 回复(1)

恶寒轻轻

无向图中，所有结点度之和=边数*2

发表于 2021-11-25 14:56:04 回复(0)

提交观点

问题信息

C++工程师 iOS工程师系统工程师安卓工程师小米集团运维工程师前端工程师算法工程师测试工程师图 2019 Java工程师

来自：小米2019秋招系统软...

上传者：小小

难度：

6条回答 381收藏 7180浏览

扫一扫，把题目装进口袋