本文主要是介绍Havel--Hakimi定理判断可图化 python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
介绍:
哈维尔[1955]——哈吉米[1962]算法可以用来判读一个度序列d是否是可图化的。
哈维尔[1955]——哈吉米[1962]定理:
对于N > 1，长度为N的度序列d能够可图化当且仅当d*能够可图化
（d*是将d中最大的度delta删除，然后将其中delta个最大的度分别减去1得到的，
最小的可图化序列式d(1) = 0。）
证明:
充分性:
若N = 1，则是平凡的。对于N > 1，假设d为d(1) ≥ d(2) ≥ ...... ≥ d(n) 。
假设简单图G*拥有度序列d*，可以在G*中添加一个顶点V，
使得V与G*中度为d(2) - 1......d(delta+1) - 1的顶点邻接。
这些d(i)是d中的delta个最大度顶点，不一定是d*中的delta个最大度顶点。
必要性:
简单图G生成度序列d，然后G生成一个子图G*有度序列d*。让w为d中最大度delta的点。
S为delta个点的集合，其中有所期望的d(2)........d(delta + 1)，如果N(w) = S
则将w删除得到G*。如果不然，则有些在S中的点与N(w)中的不相同，这时候，
可以通过在不改变每个顶点的度的情况下，改变G的画法来增加| N(w) ∩ S |的个数。
由于| N(w) ∩ S |最多增加delta次，可以重复这一过程将G转化为G#
（拥有d且S中的点为w的邻接顶点）。然后从G#中删除w得到拥有d*的G*。
由于N(w) ≠ S，可以选择点x属于S，点z∉s，且w与z有边，w与x无边。
我们希望通过在w与x之间添加边，删除w与z之间的边，但又不希望改变顶点的度。
由于d(x) ≥ d(z)并且w是z相连，则必然有一个点y与x邻接却不与z邻接。
这是采用一个2调换，添加边集{ wz, xy }，删除{ wx, yz }来增加| N(w) ∩ S |。
算法:
先将序列d逆序排序，得d(1) ≥ d(2) ≥ d(3) ≥ ........ ≥ d(n-1) ≥ d(n)。
delta = d1，将d1从d中删除，将d2一直到d（delta+1）的值都减去1得到新的度序列d*，
然后再将d*排序，循环。直到d*其中出现小于0的度，则不可能可图化，或者直到d*中全为0，则为可图化。
本质:
贪心算法
list1 = [ 4, 7, 7, 3, 3, 3, 2, 1 ]
list2 = [ 5, 4, 3, 3, 2, 2, 2, 1, 1, 1 ]def havel_hakimi_algo( degree_list ):degree_list.sort( reverse = True )print degree_listfor degree in degree_list:if degree < 0:return Falseif degree != 0:remove_val = degree_list.pop( 0 )for index in range( remove_val ):degree_list[index] -= 1havel_hakimi_algo( degree_list )return Trueprint havel_hakimi_algo( list1 )
print havel_hakimi_algo( list2 )
这篇关于Havel--Hakimi定理判断可图化 python的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
