作业帮什么是"Havel-Hakimi"算法
来源：学生作业帮 编辑：作业帮 分类：综合作业 时间：2024/11/08 14:07:02
什么是"Havel-Hakimi"算法
中文里面叫做什么算法,有什么作用?
中文里面叫做什么算法,有什么作用?
不知道中文叫什么.
Havel-Hakimi算法用来判断是否可以构造出一个满足给定顶点序列的图.例如给一个非升整数序列(4, 3, 2, 2, 2,1),该算法将判断能不能找到一个具有4个顶点的图且顶点的度可以构成上述序列.算法最终会构造出如下的图.
算法也很简单.
给定非升序列(d0, d1, d2, d3, .. dn),算法从一个有n个点没有边的图开始.n个节点与n个度一一对应.
每一次,找出还没有满足节点度要求的所有节点,按照剩余度非升排序.取出第一个节点,设其剩余度为k,则将其与随后的k个点分别连边.更新节点剩余度,如果出现负值则说明无法构造.
重复上述步骤直至所有点都满足度要求或者判定无法构造图.
Havel-Hakimi算法用来判断是否可以构造出一个满足给定顶点序列的图.例如给一个非升整数序列(4, 3, 2, 2, 2,1),该算法将判断能不能找到一个具有4个顶点的图且顶点的度可以构成上述序列.算法最终会构造出如下的图.
算法也很简单.
给定非升序列(d0, d1, d2, d3, .. dn),算法从一个有n个点没有边的图开始.n个节点与n个度一一对应.
每一次,找出还没有满足节点度要求的所有节点,按照剩余度非升排序.取出第一个节点,设其剩余度为k,则将其与随后的k个点分别连边.更新节点剩余度,如果出现负值则说明无法构造.
重复上述步骤直至所有点都满足度要求或者判定无法构造图.