弦图染色问题

关于弦图和弦图的各类应用,陈丹琦的论文中已经介绍的非常清楚。

弦图与区间图

接下来我将用自己的语言解释一下弦图的染色问题

先来说几个概念

子图: 图$G=(V,E),G’=(V’,E’),V’\subseteq V,E’\subseteq E$,则认为G’是G的一个子图

诱导子图:图$G=(V,E),G’=(V’,E’),V’\subseteq V
E={ (u,v)|u,v\in V,(u,v)\in E } $,则认为G’是G的一个诱导子图

团: 图G的一个子图$G’=(V’,E’)$,G’是关于V’的完全图
极大团: 一个团是极大团当它不是其它团的子集
最大团: 点数最多的团
我们将用 $\omega(G)$ 表示团数
最小染色:用最少的颜色使得相邻两点的颜色不同
我们将用 $\chi(G)$ 表示颜色数
弦:连接环中不相邻的两个点的边
弦图:在图中任意一个长度大于三的环都有至少一条弦

性质1:弦图的任何一个诱导子图都是一个弦图
单纯点:设N(V)表示与点V相邻的点集,V为单纯点当${V}+N(V)$的诱导子图为一个团

性质2:任何一个弦图至少有一个单纯点,不是完全图的弦图至少有两个不相邻的单纯点

完美消除序列 一个点的序列(每个点只出现一次)$(V1,V2,V3,…,Vn)$,满足 Vi 在 ${Vi,Vi+1,Vi+2,…,Vn}$的诱导子图中为一个单纯点

一个无向图是弦图当且仅当这个图有一个完美消除序列
proof
充分性:由性质2结合数学归纳法易得。
必要性:假设一个图中存在长度大于3的无弦环,且存在一个完美消除序列,设此环上有三个点:V0,V1,V2,设V0为出现在序列中的最前面一个点,有完美消除序列的性质知V1和V2相连,即该环中有弦,与环无弦矛盾。所以该无向图为弦图

寻找单纯点我们采用了MCS算法,从n到1依次给点编号,设$pow[i]$表示i与几个已标号的点相连,每次将$pow[]$最大的点标号,并更新与它相连的点的pow值。

至于染色的话直接从该序列的最后一个点染起,每个点染上可以染的最小值,即可得到最小的颜色.

1 条评论
  1. I precisely had to appreciate you once more. I’m not certain what I would have done without the actual basics documented by you directly on such question. It was before a very frightening issue for me personally, nevertheless taking a look at your expert mode you solved that took me to cry over happiness. I will be happy for this guidance and even pray you are aware of a powerful job you are carrying out instructing many others with the aid of your web blog. I am sure you have never encountered any of us.

发表一条评论