首页 > 试题广场 >

假设我们用d=(a1,a2,….a5)表示无向无自环图G的5

[单选题]
假设我们用d=(a1,a2,….a5)表示无向无自环图G的5个顶点的度数，下面给出的哪组值是可能的 
  • {3,4,4,3,1}
  • {4,2,2,1,1}
  • {3,3,3,2,2}
  • {3,4,3,2,1}
添加回答
推荐
还有多远头像 还有多远
由于题设中说没有环，所以没有自环，可以用Havel-Hakimi算法判断序列是否可图： 
def Havel(arr)
    n = len(arr)
    for i in range(n):
        seq = sorted(arr, reverse=True)
        if seq[0] >= n-i:
            return False
        for j in range(1, seq[0]+1):
            seq[j] -= 1
            if seq[j] < 0:
                return False
        arr = seq[1:]
    return True
将上述序列作为输入 
kases = [
[3,4,4,3,1],
[4,2,2,1,1],
[3,3,3,2,2],
[3,4,3,2,1]
]
for kase in kases:
    if Havel(kase):
        print(kase)
得到只有B{4,2,2,1,1}是可图的，但由B构造的图中有环，不满足“无环图”的题设，因此没有答案
编辑于 2015-07-31 18:16:08 回复(4)
牛牛12315头像 牛牛12315
无向图边数 = 各顶点度数和 / 2
所以这5个数之和必为偶数！ 只能选B
发表于 2015-09-03 19:55:09 回复(3)
FEFJay头像 FEFJay
首先要理解无自环是指一个顶点不能自己到自己，而不是图没有环，所以这题目的图是可以有环的。然后无向图边数最多和总度数最多的情况下，就是完全无向图，边数为E=n（n－1）/2条，总度数为边数的两倍即D=n（n－1）。所以只要边数小于等于E，度小于等于D，且总度数D是一个偶数，那么就都可以构成图。题目5个顶点，其完全无向图的边数为10，总度数为20，备选答案所有数字之和是偶数且不大于20的，即为答案。
编辑于 2017-03-26 13:27:07 回复(3)
直至栀子头像 直至栀子
所有顶点度的和必须为偶数
发表于 2015-08-20 10:02:19 回复(0)
CpInsist头像 CpInsist
因为是无向图，度数和为偶数；
发表于 2016-12-19 23:52:23 回复(0)
云云云一飞冲天头像 云云云一飞冲天
度不是一个随便的自然数，由于边的存在，每条边正好关联了两个顶点，如果把所有的边加起来，必然是一个偶数，而且是边数目的两倍；
发表于 2022-08-25 12:20:20 回复(0)
安科15计爱玲头像 安科15计爱玲
有向图所有的入度之和等于出度之和。而无向图不分入度出度，所以总的度数和一定是相当于有向图的入度+出度=2*入度，这一定是个偶数。只有B选项中的和是偶数，所以选B
发表于 2018-05-06 19:10:21 回复(0)
高高的围墙头像 高高的围墙
要求5个顶点的度数之和为偶数，只有第二个选项满足，虽然其构造出的图有环，但是题目要求无自环呀，所以还是满足题意的，就选B
发表于 2016-07-24 10:16:17 回复(0)
用代碼將夢想照進現實头像 用代碼將夢想照進現實
根据顶点度数之和为边数的二倍知顶点度数之和为偶数。所以选B
发表于 2018-11-20 15:26:05 回复(1)
RMrrrrrr头像 RMrrrrrr
这道题应该是没有答案的吧？B也是有环的啊，ABCD都不能选。
发表于 2016-05-09 12:38:37 回复(2)
已注销头像 已注销
无向图度数和一定为偶数
发表于 2022-03-06 19:48:15 回复(0)
Sc0tt头像 Sc0tt
所有顶点的度数和为偶数
发表于 2018-04-22 21:05:29 回复(0)
黏黏糖头像 黏黏糖
无向图的所有顶点的度之和为偶数。
发表于 2017-05-25 09:35:11 回复(0)
黎曼流形的铺头像 黎曼流形的铺
和为偶数
发表于 2017-02-10 00:22:58 回复(0)
小白2088头像 小白2088
如果有一个顶点度为4了其它顶点度都为1才满足无环。
发表于 2016-12-06 22:17:24 回复(0)
陈洪达头像 陈洪达
所有度之和只能为偶数，不可能为奇数
发表于 2016-08-16 14:36:40 回复(0)
棉花汤头像 棉花汤
度数之和为偶数
发表于 2016-08-08 11:46:36 回复(0)
zhanjxcom头像 zhanjxcom
b有环啊。4，2，2，1，1：1只能和4连，这样剩下两个2必须互连，同时必须和4连，这样不是有环么。。
发表于 2016-07-28 15:21:41 回复(4)
小乌头像 小乌
这道题没有答案啊，b是有环的。
发表于 2016-07-16 21:16:06 回复(0)
huixieqingchun头像 huixieqingchun
两个结点包含一条边，所有结点的度数之和除以2即得边数，所以度数之各一定要为偶数。
发表于 2016-05-08 22:06:26 回复(0)
nnnn头像 nnnn
因为无向图的度数和一定是偶数
发表于 2016-03-16 12:05:28 回复(0)
提交观点

问题信息

谷歌 图
上传者：大仙不醉
难度：
23条回答 17048浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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