【BZOJ1006】【HNOI2008】神奇的国度

又学了一些玄妙的东西——弦图

又%了cdq神犇的PPT

先学一下图论的一些基本概念:

子图:对于\(G=(V,E)\),\(G’=(V’,E’),V’\in V,E’\in E\)为它的子图。

诱导子图:满足\(\forall u,v\in V,(u,v)\in E\),有\((u,v)\in E’\)的子图。

团:图G的一个子图\(G’\),\(G’\)为完全图。

极大团、最大团:不是其他团子集的团;含有点数最多的团。

最小染色:用最少的颜色给点染色使得相邻点颜色不同。

最大独立集:最大的使任意两个点不相邻的点集。

最小团覆盖:能够覆盖所有点的最小团数。

那么显然有:

\(最大团大小<=最小染色\)(团中所有点必须颜色互不相同)

\(最大独立集<=最小团覆盖\)(不相邻的两个点不可能在同一个团中)

这道题用到了一些新的概念:

弦:连接环中不相邻两个点的边。

弦图:图中任意一个大于\(3\)的环都有弦的无向图。也被形象地称为三角图。

单纯点:与它所有相邻的点构成的诱导子图为团的点。

完美消除序列:每次从图中去掉一个单纯点形成的点的序列。

那么一个无向图是弦图当且仅当它有一个完美消除序列。

证明也不是很难。

那么如何求一个弦图的完美消除序列呢?这里介绍MCS算法:

设\(label[i]\)与第\(i\)个点相邻的已标号的点的个数,那么每次选择\(label[i]\)最大的点按照\(n\)到\(1\)的顺序进行标号。

具体实现可以使用链表达到\(O(n+m)\)。

对于弦图的判定,也可以在\(O(n+m)\)内解决。

那么这道题的准备工作就差不多了。

这道题是弦图的最小染色问题,只需要先求出完美消除序列再逆序对于每个点染能染的最小颜色即可。

并且可以证明,在弦图中,\(最小染色=最大团大小\)。

(有关弦图的更多知识参见cdq神犇的PPT)

说点什么

  Subscribe  
提醒