弦图算法

Published: by Creative Commons Licence

  • Tags:

导出子图

图$G=(V,E)$的导出子图$G'=(V',E')$,需要满足,$V'\subset V$,且$E'={(u,v)|(u,v)\in E \land u\in V'\land v\in V'}$。

一个无向图中的一个导出子图如果是完全图,则称改导出子图为团。

最大独立集

最大独立集是指V的一个子集,使得其中元素两两之间没有边存在。

最小团覆盖

最小团覆盖是指将V切分为尽可能少的不相交集合。

环上连接两个环上不相连的顶点的边称为弦。

弦图

一个无向图中任意长度大于3的环都至少有一个弦,这样的无向图称为弦图。

弦图的导出子图一定也是弦图

单纯点

设$N(v)$表示与点$v$相邻的点集,一个点称为单纯点当${v}+N(v)$的导出子图是一个团。

任何一个弦图都至少有一个单纯点

完美消除序列

对于无向图$G=(V,E)$,设$n=|V|$。图的完美消除序列为${v_1,v_2,\ldots ,v_n}$。满足对于任意$i$,$v_i$为${v_i,v_{i+1},\ldots ,v_n}$的导出子图的一个单纯点。

一个无向图是弦图当且仅当图存在完美消除序列

最大势算法

最大势算法可以以$O(|V|+|E|)$的时间复杂度判断一个图是否是弦图,如果是还能同时找到图的完美消除序列。

算法原理不清楚,这里直接将一下算法怎么实现。

n = |V|;
m = |E|;
A = empty-set
B = V
for(i = n - 1; i >= 0; i--){
	在B中找到x满足与x相邻的元素组成的集合N(x)与V的交集大小最大
	将x标记为i
	将x从B移到A
}
for(i = 0; i < n; i++){
	记x为被标记为i的结点
	设C为与x相邻且编号大于i的所有顶点组成的集合
	设y为集合C中编号最小的顶点
	如果C中存在某个顶点zz不是y且z与y没有边那么这个图就不是弦图退出
}
这个图是弦图并找到了完美消除序列

弦图点染色问题

要计算弦图的染色数,只需要逆序遍历完美消除序列,为每个顶点染色尽可能小的颜色即可。

弦图最大独立集

弦图中的最大独立集可以通过按序遍历完美消除序列,并以贪心的方式选取尽可能多的元素。

set = 空集
for(i = 0; i < n; i++){
    记x表示被标记为i的顶点;
    如果x某个邻接的顶点属于set则跳过否则将x加入到set中
}
return set

弦图最小团覆盖

设弦图最大独立集为${v_1, v_2, \ldots, v_k}$,那么弦图的最小团覆盖为${v_1+N(v_1), v_2+N(v_2), \ldots, v_k + N(v_k)}$。

参考资料