首页 > 试题广场 >

回答问题

[单选题]
设 ，其中 di 为非负整数，i=1,2,…n 。若存在 n 个顶点的(简单)无向图,使得顶点 vi 的度为 di，则称 d 是可图解的。下面给出的各序列中哪个是可图解的？ 
  • (0，1，1，2，,3，3)；
  • (1，1，2，2，3);
  • (0，1，3，3，3)；
  • (1，3，4，4，5)。
查看正确选项
添加回答
[boring]头像 [boring]
这个是离散数学中图论部分的内容
可图解就是可图化
 1：非负整数d=(d1,d1,...dn)是可图化的当且仅当 ∑di （i:1...n）为偶数
                所以，先排除B,D
                B:1+1+2+2+3 结果奇数，同理D
:2：若n阶无向简单图，则∆（G）<=n-1 （∆（G）：无向图的最大度）
                可知C：n=5   ，∆（G）=3    5-1<=3   ok 。而其中一个度=0；相当于只有 n=4  4-1 <=3 ok。
                同理A。
然后，因为A,C都满足这两个条件，然后，就只能通过画图判断，很容易就知道，C选项是不可能的（画不出来）。
所以，选择A。


发表于 2017-11-21 22:37:31 回复(5)
更多回答
karaysn头像 karaysn
不会，哪位同学解答一下，谢谢啦
发表于 2017-11-21 18:48:34 回复(0)
弘毅258头像 弘毅258

图片说明

发表于 2020-09-10 15:46:30 回复(0)
Sc0tt头像 Sc0tt
首先根据无向图中每个定点的度之和为偶数可以排除BD选项，其次对于C选项，题目要求是无向简单图，因此不能够有自环，不满足。
发表于 2018-05-18 09:35:15 回复(0)
鲜土豆头像 鲜土豆
BD排除，对于AC画一下就能看出来了
发表于 2018-05-20 10:28:11 回复(0)
侯卿头像 侯卿
首先所有顶点度和为边数2倍(偶数)，所以排除BD。至于C，后三个就算两两相连还多出三条分支，而剩余度数和都不够3，排除。
编辑于 2018-04-19 10:00:05 回复(0)
别踩我尾巴头像 别踩我尾巴
首先，只有一个节点时度为0，排除两个选项，无向图三个节点时，节点度不会为三，就a了
发表于 2022-07-09 11:18:42 回复(0)
潜水系的徐先森头像 潜水系的徐先森
<p>无向图，</p><p>1、顶点度数之和为边数的2倍，所以度之和一定为偶数，</p><p>2、由于简单图不存在重边，所以最大顶点度数为总顶点数-1</p><p>其余画图吧，啊哈哈哈哈哈哈，此外救不了你了</p>
发表于 2020-12-21 13:42:01 回复(0)
笑笑加油鸭头像 笑笑加油鸭
无向图的话度之和肯定是偶数，那就排出了BD了，AC画一下就可以了
发表于 2020-07-16 17:16:53 回复(0)
徐立明头像 徐立明
Havel-Hakimi定理
发表于 2019-12-03 10:17:41 回复(0)
我会回来的呢头像 我会回来的呢

哪位大神可以把A图画一下

发表于 2019-08-30 08:14:36 回复(0)
提交观点

问题信息

图
上传者：赞花婆
难度：
11条回答 3101浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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