首页 > 其他 > 详细

havel定理

时间:2020-06-19 21:33:55      阅读:92      评论:0      收藏:0      [点我收藏+]

定义:给定一个非负整数序列{dn},若存在一个无向图使得图中各点的度与此序列一一对应,则称此序列可图化。进一步,若图为简单图,则称此序列可简单图化
具体操作方法:

  • 1.我们把所有度数列进行升序排序
  • 2.从最大的度数开始, 把当前最大的度数去掉, 其他的度数-1
  • 3.判断当剩下的度数中有负数的存在\(则无法可简单图化\) ,反之, 没有的话继续进行如果\(结束都没有出现负数就代表可以可图化\)
    例子一:
给出序列序列:

4 7 7 3 3 3 2 1
降序排序

7 7 4 3 3 3 2 1
删除第一个数字7,将其后7个数都减去1,并重新排序

6 3 2 2 2 1 0
重复步骤

2 1 1 1 0 -1
发现有负数,则这个序列不能组成简单图

例子二:

5 4 3 3 2 2 2 1 1 1
删除数字5,将其后5个数都减去1,并重新排序

3 2 2 2 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 0
…以此类推,直至

0 0 0
所以可以组成简单图

havel定理

原文:https://www.cnblogs.com/gaohaoy/p/13166346.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!