如何判断是无向简单图的度数列?
例如:(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)排除
其次,最高度数小于节点个数。
满足这两点的就要结合图来判断。比如(1,3,3,3),选取任意一点A为3度点,剩下的BCD点都是1度,可选择其中一个为最终1度点,比如B,那么剩下的CD两点要变成3度的。而A,B的度数不能改变,所以CD由1度变成3度,只能是在两点之间加两条边,这样就出现了平行边,图不是简单图。所以(1,3,3,3)可以是某个无向图的度数序列,但不是无向简单图的度数序列。
其次,最高度数小于节点个数。
满足这两点的就要结合图来判断。比如(1,3,3,3),选取任意一点A为3度点,剩下的BCD点都是1度,可选择其中一个为最终1度点,比如B,那么剩下的CD两点要变成3度的。而A,B的度数不能改变,所以CD由1度变成3度,只能是在两点之间加两条边,这样就出现了平行边,图不是简单图。所以(1,3,3,3)可以是某个无向图的度数序列,但不是无向简单图的度数序列。
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询