给定一个非负整数序列,若存在一个无向图使得图中各点的度与此序列一一对应,则称此序列可图化。进一步,若图为简单图,则称此序列可简单图化。
可图化的判定比较简单:
。
关于具体图的构造,我们可以简单地把奇数度的点配对,剩下的全部搞成自环。
可简单图化的判定,有一个Havel定理,是说: 我们把序列排成不增序,即
则d可简单图化当且仅当
可简单图化。这个定理写起来麻烦,实际上就是说,我们把d排序以后,找出度最大的点(设度为d1),把它和度次大的d1个点之间连边,然后这个点就可以不管了,一直继续这个过程,直到建出完整的图,或出现负度等明显不合理的情况。
定理的简单证明如下:
(<=)若d'可简单图化,我们只需把原图中的最大度点和d'中度最大的d1个点连边即可,易得此图必为简单图。 (=>)若d可简单图化,设得到的简单图为G。分两种情况考虑:
(a)若G中存在边,则把这些边除去得简单图G',于是d'可简单图化为G'
(b)若存在点Vi,Vj使得i=dj,必存在k使得(Vi, Vk)在G中但(Vj,Vk)不在G中。这时我们可以令GG=G-{(Vi,Vk),(V1,Vj)}+{(Vk,Vj),(V1,Vi)}。GG的度序列仍为d,我们又回到了情况(a)。
题目练习:http://acm.hdu.edu.cn/showproblem.php?pid=2454
posted on 2008-11-02 17:06
小果子 阅读(1240)
评论(0) 编辑 收藏 引用 所属分类:
学习笔记