无向图的度数列和无向简单图的度数列_无向图顶点和度的关系

无向图的度数列和无向简单图的度数列_无向图顶点和度的关系在已知度序列的情况下,如何判断它是否为简单无向图呢?第一步·判断是否为无向图利用握手定理及其推论:1.无向图的顶点度数之和等于边数的两倍。2.对于无向图,有奇数个度的顶点必为偶数个。凡是不满足的,就不是无向图。第二步·判断是否为简单图这里需要用到Havel定理。由于此定理的文字表述过于复杂,故在此只给出方法。1.对已知的度序列进行降序排列(相等的放在一起)。2.假设最大的...

感谢评论区大佬@goodloveyourlove补充的判断度数列是否能构成无向树的方法与例子。

关于度数列是否能构成无向树的判断方法可以移步至评论区。

==============================================

在已知度数列的情况下,如何判断它是否为简单无向图?

第一步·判断是否为无向图

利用握手定理及其推论:

1.无向图的顶点度数之和等于边数的两倍。
2.对于无向图,有奇数个度的顶点必为偶数个。
凡是不满足的,就不是无向图。

第二步·判断是否为简单图

判断是否为简单图即判断是否可图化,
而可图化的判断则需要用到Havel–Hakimi定理
由于此定理的文字表述较为复杂,故在此只给出方法。

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

下面给出几个例子

一. 1,1,1,2,3
显然度数之和为偶数,也有偶数个奇数度。
首先进行降序排列:3,2,1,1,1
删去最大度数3,将其后面的3个度数减一:1,0,0,1
重新排序:1,1,0,0
删去最大数1,将其后面的1个度数减一:0,0,0
发现最后所有度数都变成了0,则可以构成简单无向图。

二.2,2,2,2,2
显然度数之和为偶数。
首先进行降序排列:2,2,2,2,2
删去最大度数2,将其后面的2个度数减一:1,1,2,2
重新排序:2,2,1,1
删去最大度数2,将其后面的2个度数减一:1,0,1
重新排序:1,1,0
删去最大度数1,将其后面的1个度数减一:0,0
发现最后所有度数都变成了0,则可以构成简单无向图。

三.1,3,3,3
显然度数之和为偶数,也有偶数个奇数度。
首先进行降序排列:3,3,3,1
删去最大度数3,将其后面的3个度数减一:2,2,0
无需重新排序。
删去最大度数2,将其后面的2个度数减一:1,-1
发现出现了负数,则仅仅构成无向图,不能构成简单无向图。

架构君码字不易,如需转载,请注明出处:https://javajgs.com/archives/165744
0
 

发表评论