区间图弦图和完美图.ppt

《区间图弦图和完美图.ppt》由会员分享，可在线阅读，更多相关《区间图弦图和完美图.ppt（46页珍藏版）》请在三一办公上搜索。

1、区间图、弦图和完美图介绍,内容介绍,在本讲中将主要介绍区间图(interval graph)区间图上的色数(chromatic number)和最大团问题(maximum clique)完美消除序列(perfect elimination order)弦图(chordal graph)及其判定区间图的判定完美图(perfect graph),区间图 POJ1083,POJ1083 Moving Tables,一个公司有400个房间，布局如上图所示。编号为奇数的房间在背面，编号为偶数的房间在南面，中间被一条走廊隔开。现在公司要将某些桌子从一个房间移动到另一个房间。走廊很窄，如果两张桌子需要经过同

2、一段走廊的话，那么它们不能同时移动。每移动一张桌子需要10分钟。问最少需要多久才能将所有桌子移动完毕。,区间图 POJ1083,Moving：2-45-1412-106-1,2 4,6 1,5 14,12 10,求一般图的色数是NP难问题！,区间图 定义,一个区间是有两个端点的线段，端点可以是开的或闭的。给定一些区间，可以定义一个相交图。定义1：给定一些区间，定义一个相交图的每个顶点v代表一个区间Iv,顶点(v,w)间有边，当且仅当Iv交Iw非空。定义2：一个图G是区间图，如果它是若干区间的相交图。,区间图 例,区间图的例子,不是区间图的例子,区间图 顶点排序,定理1：开区间、闭区间、半开闭区

3、间对应的区间图是等价的。证明思路：由于区间在连续的实数轴上，我们可以对区间做小量伸缩而不影响相交情况,区间图 顶点排序,推论1：任何区间图G都存在一个没有重点的区间表示于是我们可以将G的顶点按其代表区间的左端点排序，称之为区间图G顶点的自然排序,区间图 顶点排序,区间图 顶点排序,定义2：Pred(Vi)=Vj|(Vi,Vj)E j i 为顶点Vi的前驱Vi Pred(Vi)是一个团,区间图 最小染色算法,令v1,v2.vn为顶点的一个自然排序，一下算法得到区间图G的一个最小染色,完美消除序列,定义：一个顶点序列V1.Vn如果对任意i满足Pred（Vi）是一个团，那么这种序列称为完美消除序列。

4、,最大团最大独立集最小覆盖最小团覆盖,弦图,定义：如果一个图的任何诱导子图都不是K阶环（K=4），那么该图称为弦图,弦图与完美消除序列,定理：如果一个图G具有完美消除序列，则G是弦图。,弦图与完美消除序列,定理：图G是弦图，当且仅当G具有完美消除序列,弦图与完美消除序列,定义：如果与顶点V相邻的所有顶点构成一个团，则V称为单纯点引理1：任何弦图G具有至少一个单纯点。如果G不是完全图，那么它至少具有两个不相邻的单纯点。引理2：弦图的任何诱导子图都是弦图。,弦图与完美消除序列,引理1：任何弦图G具有至少一个单纯点。如果G不是完全图，那么它至少具有两个不相邻的单纯点。,弦图与完美消除序列,最大势算法

5、(MCS)字典序广度优先搜索(Lexicographical BFS),弦图与完美消除序列,LexBFS,A,D,C,B,E,F,G,H,J,K,I,L,弦图的判定,LexBFS O(n+m),1.令Vi是第一个桶中的第一个元素(显然Vi是目前标号最大的一个顶点)。2.将Vi从桶S(L(Vi)中删去。3.如果S(L(Vi)已空，将它从Q中删去。4.对于每个Vi的相邻点W：5.如果W仍在Q中(W尚未选择，必须更新它的标号和在Q中的位置)6.找到S(L(W)以及它在Q中的位置。7.寻找Q中S(L(W)上一个桶。8.如果这样的桶不存在,或它不是 S(L(W)i)9.在Q中的当前位置建立一个桶S(L(

6、W)i)10.将W从S(L(W)中取出并加入S(L(W)i)中 11.如果S(L(W)已空，将它删除。12.将L(W)更新为L(W)i。,弦图的判定,检验 O(n+m),弦图的判定,ZOJ Fishing Net判断一个图是不是弦图,再谈区间图,定理：以下命题是等价的：(1)G是区间图(2)G是弦图，且G是伴相似图(co-comparability graph)。(3)G的极大团可以连续地编号。即我们可以将它们排为C1.Ck，满足对于任何vV，序列j|j1.k，vCj是连续整数集。,再谈区间图,定义：一个能够无环且具有传递性地定向的无向图G称为相似图。定理：(1)-(2)定理：(3)-(1)I

7、(V)=Mini|VCi，Max i|VCi,再谈区间图,定理(2)-(3)令G是G补图经过无环传递定向后的有向图。构造有向图H.V(H)=C,E(H)存在xC1,yC2 且G,再谈区间图,定理：H是传递的,再谈区间图,定理：H是无环的,再谈区间图,定理：H的一个拓扑排序C1,C2,Ck是满足(3)的一个序列,区间图的判定,区间图的判定,定理：设G是弦图，M是G的一个极大团，则存在i，M=Vi Pred(Vi)定理：ViPredVi是极大团，当且仅当对Vi的任何后继Vj，至少有一个Vi的前驱不是Vj的前驱。,区间图的判定,连续1性质(consecutive ones property,COP

8、or C1P)POJ2790：判断一个矩阵是否具有C1PAnm，aij=1 Vi Cj01010 01000 10101 10100 00011 00101,区间图的判定,N=4S1=2,3,S2=3,4,区间图的判定,PQ-tree,http:/,区间图的判定,pertinent-root,区间图的判定,L1当前节点是叶子标记为full,区间图的判定,P1当前节点是P-node,子节点都是full标记为full,区间图的判定,P2P-node,pertinent-root,full+empty增加新的P-node作为full子节点的父节点及当前节点的子节点(如果只有1个full子节点则不增加

9、新的P-node),区间图的判定,P3P-node,not pertinent-root,full+empty当前节点标记为partial Q-node,增加新的P-node作为full子节点的父节点及当前节点的子节点,增加新的P-node作为empty子节点的父节点及当前节点的子节点,区间图的判定,P4P-node,pertinent-root,1 partial+full+empty,区间图的判定,P5P-node,not pertinent-root,1 partial+full+empty,区间图的判定,P6P-node,pertinent-root,2 partial+full+empty,区间图的判定,Q1Q-node,all full,区间图的判定,Q2Q-node,0/1 partial+连续full+empty,区间图的判定,Q3Q-node,2 partial+连续full+empty,完美图,定义：一个图G是完美图，如果W(G)X(G)，且对于G的任意诱导子图H，都有W(H)X(H)。,强完美图定理,强完美图定理(SPGT)一个图是完美图，当且仅当它的任何大于3的诱导子图都不是奇阶洞或奇阶反洞,