如何判断是无向简单图的度数列?例如:(1)5,4,3,2,1; (2)1,3,3,3 哪个可以构成无向简单图的度数列?

如何判断是无向简单图的度数列?例如:(1)5,4,3,2,1; (2)1,3,3,3 哪个可以构成无向简单图的度数列?
如何判断是无向简单图的度数列?
例如:(1)5,4,3,2,1; (2)1,3,3,3 哪个可以构成无向简单图的度数列?

如何判断是无向简单图的度数列?例如:(1)5,4,3,2,1; (2)1,3,3,3 哪个可以构成无向简单图的度数列?
首先,根据握手定理,度数之和必须是偶数；(5,4,3,2,1)排除
其次,最高度数小于节点个数.
满足这两点的就要结合图来判断.比如(1,3,3,3),选取任意一点A为3度点,剩下的BCD点都是1度,可选择其中一个为最终1度点,比如B,那么剩下的CD两点要变成3度的.而A,B的度数不能改变,所以CD由1度变成3度,只能是在两点之间加两条边,这样就出现了平行边,图不是简单图.所以(1,3,3,3)可以是某个无向图的度数序列,但不是无向简单图的度数序列.