区间图弦图和完美.pptVIP

弦图与完美消除序列引理1：任何弦图G具有至少一个单纯点。如果G不是完全图，那么它至少具有两个不相邻的单纯点。弦图与完美消除序列最大势算法(MCS)字典序广度优先有哪些信誉好的足球投注网站(LexicographicalBFS)弦图与完美消除序列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(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–FishingNet判断一个图是不是弦图弦图的判定G是区间图G是弦图，且G是伴相似图(co-comparabilitygraph)。G的极大团可以连续地编号。即我们可以将它们排为C1..Ck，满足对于任何v∈V，序列{j|j∈{1..k}，v∈Cj}是连续整数集。定理：以下命题是等价的：再谈区间图定义：一个能够无环且具有传递性地定向的无向图G称为相似图。定理：(1)-(2)定理：(3)-(1)I(V)=[Min{i|V∈Ci}，Max{i|V∈Ci}]再谈区间图再谈区间图定理(2)-(3)令G’是G补图经过无环传递定向后的有向图。构造有向图H.V(H)=C,C1,C2∈E(H)?存在x∈C1,y∈C2且x,y∈G’再谈区间图定理：H是传递的再谈区间图定理：H是无环的再谈区间图定理：H的一个拓扑排序C1,C2,…Ck是满足(3)的一个序列区间图的判定定理：设G是弦图，M是G的一个极大团，则存在i，M={Vi}∪Pred(Vi)定理：{Vi}∪Pred{Vi}是极大团，当且仅当对Vi的任何后继Vj，至少有一个Vi的前驱不是Vj的前驱。0201区间图的判定区间图的判定连续1性质(consecutiveonesproperty,COPorC1P)POJ2790：判断一个矩阵是否具有C1PAnm，aij=1?Vi∈Cj01010

01000

10101

10100

00011

00101N=4S1={2,3}{1,2,3,4,1,3,2,4,1,4,2,3,1,4,3,2,2,3,1,4,2,3,4,1,3,2,1,43,2,4,1,4,1,2,3,4,1,3,2,4,2,3,1,4,3,2,1}S2={3,4}{1,2,3,4,1,4,3,2,2,3,4,1,4,3,2,1}12345区间图的判定区间图的判定PQ-tree/2008/11/pq-tree-algorithm-and-consecutive-ones.html区间图、弦图和完美图介绍区间图上的色数(chromaticnumber)和最大团问题(maximumclique)弦图(chordalgraph)及其判定区间图(intervalgraph)完美消除序列(perfecteliminationorder)区间图的判定完美图(perfectgraph)010203040506在本讲中将主要介绍内容介绍区间图–POJ1083[POJ1083]MovingTables一个公司有400个房间，布局如上图所示。编号为奇数的房间在背面，编号为偶数的房间在南面，中间被一条走廊隔开。现在公司要将某些桌子从一个房间移动到另一个房间。走廊很窄，如果两张桌子需要经过同一段走廊的话，那么它们不能同时移动。每移动一张桌子需要10分钟。问最少需要多久才能将所有桌子移动完毕。区间图–POJ1083Moving：2-45-1412-106-124615141210求一般图的色数是NP难问题！01一个区间是有两个端点的线段，端点可以是开的或闭的。给定一些区间，可以定义一个相交图。02定义1：给定一些区间，定义一个相交图的每个顶点v代表一个