今天在gym上被一题疑似弦图的题目卡了一下，后来猛犸随便乱搞就搞过去了。看了一下gcj上的solution，发现有用完美消除序列过的，于是就去温习了一下弦图。结果最后发现其实那个图根本不是弦图……只是碰巧那个最大势的方法求出来的顺序是靠谱的染色顺序罢了。写一下今天温习的内容吧。
- 弦图的定义。任意size>3的环都存在弦。弦即环上不相邻两点之间的边。
- 完美消除序列。$$v_i$$和$$v_{i+1}, … , v_n$$构成的诱导子图里，把和$$v_i$$相连的点拿出来，会成为一个团。
- 完美消除序列的求法。令$$d_i = 0$$，然后每次选取d值最大的一个点拿出来放进序列头，再枚举该点的出边，把他们的d值加1。如此反复。
-
完美消除序列的性质
- 按序列从后往前染色可得图的色数。在弦图里，色数等于最大团的size。
- 按序列从前往后贪心取可得最大独立集。在弦图里，最大独立集额等于最小团覆盖。
- 按上面最大势方法求出这个序列顺序以后，如果想知道该图是不是弦图，那么枚举每个点$$v_i$$，假设他在$$v_{i+1}, …, v_n$$里有边直接相连的点集为$$S = {x_1, x_2, … , x_m}$$然后只需判定$$x_1$$是不是和$$x_2, x_3, … , x_m$$都有边就可以了。
- 完美图的定义。所有诱导子图满足色数等于最大团size的图。
- 伴完美图的定义。所有诱导子图满足最大独立集等于最小团覆盖的图
- 区间图总是弦图。并且按r排序就是他的完美消除序列。
- 其实感觉很多不是弦图的题要求色数都可以用最大势的方法求出顺序然后贪心染……说不定就凑出正解的顺序过了……比如GCJ2009 R3 C