首页 > 试题广场 >

下面四组数能构成无向简单图的度数列的有（）。

[单选题]

查看正确选项

一个像夏天li

B也是正确的，它只是构成了一个5-圈。简单图的定义是不含环和平行边

发表于 2018-05-30 11:31:47 回复(1)

帅帅的尾

BC都对

发表于 2019-07-30 09:48:57 回复(0)

2fang

首先要求所有数(度)之和是偶数：【任意无向图所有顶点度数之和等于边数的2倍】排除A
其次判断是否为简单图：既无平行边、也无环的图才是简单图。
C: （2,2,2）构成环，（1,1）是单独的一条线段，排除
D:（0,1,3,3,3）v1单独出来，v4和v5之间具有平行边，重数=2，排除。

发表于 2017-06-14 11:02:31 回复(1)

小凛ovo

可以利用Havel-Hakimi定理判断：

1.对已知的度数列进行降序排列（相等的放在一起）。
2.假设最大的度为k（已经排在首位），删去最大的度数k，对后面的k个度数都进行减1，再进行降序排列，由此得到一个新度数列。
3.重复第2步的操作。
4.若在此期间出现了负数，则不是简单图；若最后剩下的度数列的度数均为0.则为简单图。

发表于 2021-03-22 20:06:44 回复(1)

yglbs

选C，可以连成一条直线的形状

A的度没办法组合成无向图排除，B构成环了排除，D存在平行边排除

发表于 2017-09-28 18:55:08 回复(0)

提交观点

问题信息

组合数学

上传者：赞花婆

难度：

5条回答 88收藏 6464浏览

扫一扫，把题目装进口袋