注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

弦图 团数=色数  

2014-03-06 20:32:41|  分类: 总结 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
        最早学这个,是刚开始刷bzoj的时候,试图学vfleaking那样顺着做的日子里遇到的hnoi2008的题。
        我看了一晚上的cdq的论文:《弦图与区间图》,然后问了陈胤伯(应该没记错?)这么一个问题
        “团数是什么啊?”
……
“就是最大团的元素个数”
“哦……”
然后就照着结论A掉了

        然后上学期看《组合数学》,发现了这东西的详细证明并学会了
一问发现好像身边没几个人管过这东西?算了……反正学了不是坏事
结果今天竟然在贴吧里看到有人来问这个了……本想回复的突然发现百度贴吧那地方方便放么?
于是来赶了一篇
如果没看懂的话可以自行翻阅《组合数学》,个人感觉这篇文章就是《组合数学读书笔记之弦图》
事先声明……《组合数学》肯定会有东西翻译的跟信息里不一样。应该不是数学和信息学科之间的矛盾,而是信息学翻译成中文和数学翻译成中文的矛盾……《组合数学》里最让我无语的就是所有的贪心算法都被翻译成了贪婪算法,大家可以脑补里面讲最小生成树的时候“构造一棵最小生成树的贪婪算法”是多么毁三观

定义:
色数:给图染色相邻点异色的最小可行的颜色数,记为χ(G)
团:一个完全图
团数:最大团的元素个数,记为ω(G)
最大独立集:最大的集合里面元素互不相邻,记为α(G)
团划分数:用最少的团划分整个图,记为θ(G)
χ-完美:一个图的任意导出子图H有性质χ(H)=ω(H)
θ-完美:一个图的任意导出子图H有θ(H)=α(H)

下面开始 证明
首先是扯淡时间
组合数学上说1961年有个叫Berge的人提出猜想:只存在一种完美性……也就是那两种完美是共存亡的
然后一个叫弦图 团数=色数 - ydc - ydc的博客的人把他证出来了
于是我们陈述这个事实而不加证明……
现在有了那个名字都不知道怎么打出来的人帮忙……我们定义完美图:任意导出子图有兴致χ(H)=ω(H),θ(H)=α(H)
        于是人类开始思考那些东西是完美图了
完全图是完美图?显然
二分图是完美图?显然
区间图是完美图?可以证明区间图是弦图,我们如果证明了弦图是完美图区间图就显然了
现在看弦图(终于步入正题了)
我们定义关节集:一个点的集合,干掉这些点之后的导出子图是不联通的
极小关节集:不能变得更小的一个关节集
我们先证明引理:
G=(V,E)是连通图,U是他的一个关节集,假设U的导出子图还是个团。干掉U之后剩下t个联通块,分别设为G1=(U1,E1),G2=(U2,E2)……Gt=(Ut,Et),并假设对于任意导出子图G(Ui∪U)满足χ(Ui∪U)=ω(Ui∪U)的……那么G就是个完美图
证明:
先吐槽这个引理有这么多假设
令k=ω(G),因为G(Ui∪U)的每个团也是G的团所以ω(Ui∪U)<=k
由于Ui和Uj的点互不相邻,所以至少存在j满足ω(Uj∪U)=k……其实ω(G)就是max{ω(U1∪U),ω(U2∪U)……ω(Ut∪U)}对吧,当然χ(G)也就是max{χ(U1∪U),χ(U2∪U),……,χ(U3∪U)}
由于前面那么多假设,所以这么苛刻的情况下很显然就有χ(G)=ω(G)了
于是我们有了证明一个图是完美图的方向……接下来试着证证弦图满足这些就行了
第一个假设是找到一个关节集的导出子图是个团,我们证明这么一个定理:设G=(V,E)是个联通的弦图U是极小关节集,那么U的导出子图是个完全图
U里面随便抓两个点a,b出来,现在删了这个关节集,图至少要有两个联通分块G1=(U1,E1)和G2=(U2,E2)。由于是极小,所以a,b一定要和G1,G2都有边,否则可以让他更小
存在一条路线为a->G1->b的链,一条路线为a->G2->b的链,它们构成一个长度>=4的环
由于是弦图,我们需要在环里不断加边……由于G1,G2之间无边,最后可以发现,a,b必须有边
然后就可以上数学归纳法证明它是完美的了:
一个点的弦图显然是完美的
假设n-1个点的弦图一定是完美的……现在是一个n个点的弦图
特判掉完全图的情况 
他必定存在一个是完全图的极小关节集U……
因为弦图的导出子图必须是弦图……所以套用之前的引理,我们把它变成t个导出子图G1=(U1,E1),G2=(U2,E2)……Gt=(Ut,Et)
G1,G2……Gt都是完美图,然后G就是完美图了
数学家们屌爆了
  评论这张
 
阅读(587)| 评论(5)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017