最新区间图弦图和完美图精品课件.ppt
内容介绍 在本讲中将主要介绍 区间图(interval graph) 区间图上的色数(chromatic number)和最大团问题(maximum clique) 完美消除序列(perfect elimination order) 弦图(chordal graph)及其判定 区间图的判定 完美图(perfect graph)区间图 顶点排序2 41 65 1412 10v2v1 v3v4区间图 顶点排序 定义2：Pred(Vi) = Vj | (Vi, Vj) E j =4），那么该图称为弦图弦图与完美消除序列 定理：如果一个图G具有完美消除序列，则G是弦图。弦图与完美消除序列 定理：图G是弦图，当且仅当G具有完美消除序列弦图与完美消除序列 定义：如果与顶点V相邻的所有顶点构成一个团，则V称为单纯点 引理1：任何弦图G具有至少一个单纯点。如果G不是完全图，那么它至少具有两个不相邻的单纯点。 引理2：弦图的任何诱导子图都是弦图。弦图与完美消除序列 引理1：任何弦图G具有至少一个单纯点。如果G不是完全图，那么它至少具有两个不相邻的单纯点。弦图与完美消除序列 最大势算法(MCS) 字典序广度优先搜索(Lexicographical BFS)弦图与完美消除序列 LexBFSA, 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 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(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 or C1P) POJ2790：判断一个矩阵是否具有C1P Anm ，aij = 1 Vi Cj 01010 01000 10101 10100 00011 00101 区间图的判定 N = 4 S1=2, 3 , S2=3, 4 ,区间图的判定 PQ-treehttp:/ L1 当前节点是叶子 标记为full区间图的判定 P1 当前节点是P-node,子节点都是full 标记为full区间图的判定 P2 P-node,pertinent-root,full + empty 增加新的P-node作为full子节点的父节点及当前节点的子节点(如果只有1个full子节点则不增加新的P-node)区间图的判定 P3 P-node,not pertinent-root,full + empty 当前节点标记为partial Q-node,增加新的P-node作为full子节点的父节点及当前节点的子节点,增加新的P-node作为empty子节点的父节点及当前节点的子节点,区间图的判定 P4 P-node,pertinent-root,1 partial + full + empty区间图的判定 P5 P-node,not pertinent-root,1 partial + full + empty区间图的判定 P6 P-node,pertinent-root,2 partial + full + empty区间图的判定 Q1 Q-node,all full区间图的判定 Q2 Q-node,0/1 partial + 连续full + empty区间图的判定 Q3 Q-node, 2 partial + 连续full + empty完美图 定义：一个图G是完美图，如果W(G)X(G)，且对于G的任意诱导子图H，都有W(H)X(H)。 强完美图定理 强完美图定理(SPGT) 一个图是完美图，当且仅当它的任何大于3的诱导子图都不是奇阶洞或奇阶反洞
