什么是"Havel-Hakimi"算法中文里面叫做什么算法,有什么作用?
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/04 00:03:26
![什么是](/uploads/image/z/9471135-39-5.jpg?t=%E4%BB%80%E4%B9%88%E6%98%AF%22Havel-Hakimi%22%E7%AE%97%E6%B3%95%E4%B8%AD%E6%96%87%E9%87%8C%E9%9D%A2%E5%8F%AB%E5%81%9A%E4%BB%80%E4%B9%88%E7%AE%97%E6%B3%95%2C%E6%9C%89%E4%BB%80%E4%B9%88%E4%BD%9C%E7%94%A8%3F)
什么是"Havel-Hakimi"算法中文里面叫做什么算法,有什么作用?
什么是"Havel-Hakimi"算法
中文里面叫做什么算法,有什么作用?
什么是"Havel-Hakimi"算法中文里面叫做什么算法,有什么作用?
不知道中文叫什么.
Havel-Hakimi算法用来判断是否可以构造出一个满足给定顶点序列的图.例如给一个非升整数序列(4, 3, 2, 2, 2,1),该算法将判断能不能找到一个具有4个顶点的图且顶点的度可以构成上述序列.算法最终会构造出如下的图.
算法也很简单.
给定非升序列(d0, d1, d2, d3, .. dn),算法从一个有n个点没有边的图开始.n个节点与n个度一一对应.
每一次,找出还没有满足节点度要求的所有节点,按照剩余度非升排序.取出第一个节点,设其剩余度为k,则将其与随后的k个点分别连边.更新节点剩余度,如果出现负值则说明无法构造.
重复上述步骤直至所有点都满足度要求或者判定无法构造图.