1、區間圖、弦圖和完美圖介紹內容介紹在本講中將主要介紹區間圖(interval graph)區間圖上的色數(chromatic number)和最大團問題(maximum clique)完美消除序列(perfect elimination order)弦圖(chordal graph)及其判定區間圖的判定完美圖(perfect graph)區間圖 POJ1083POJ1083 Moving Tables一個公司有400個房間，布局如上圖所示。編號為奇數的房間在背面，編號為偶數的房間在南面，中間被一條走廊隔開。現在公司要將某些桌子從一個房間移動到另一個房間。走廊很窄，如果兩張桌子需要經過同一段走廊的

2、話，那么它們不能同時移動。每移動一張桌子需要10分鐘。問最少需要多久才能將所有桌子移動完畢。區間圖 POJ1083Moving：2 - 45 -1412 - 106 - 1 2 46 15 1412 10求一般圖的色數是NP難問題！區間圖 定義一個區間是有兩個端點的線段，端點可以是開的或閉的。給定一些區間，可以定義一個相交圖。定義1：給定一些區間，定義一個相交圖的每個頂點v代表一個區間Iv,頂點(v,w)間有邊，當且僅當Iv交Iw非空。定義2：一個圖G是區間圖，如果它是若干區間的相交圖。區間圖 例區間圖的例子不是區間圖的例子區間圖 頂點排序定理1：開區間、閉區間、半開閉區間對應的區間圖是等價的

3、。證明思路：由于區間在連續的實數軸上，我們可以對區間做小量伸縮而不影響相交情況區間圖 頂點排序推論1：任何區間圖G都存在一個沒有重點的區間表示于是我們可以將G的頂點按其代表區間的左端點排序，稱之為區間圖G頂點的自然排序區間圖 頂點排序2 41 65 1412 10v2v1 v3v4區間圖 頂點排序定義2：Pred(Vi) = Vj | (Vi, Vj) E j =4），那么該圖稱為弦圖弦圖與完美消除序列定理：如果一個圖G具有完美消除序列，則G是弦圖。弦圖與完美消除序列定理：圖G是弦圖，當且僅當G具有完美消除序列弦圖與完美消除序列定義：如果與頂點V相鄰的所有頂點構成一個團，則V稱為單純點引理1：

4、任何弦圖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

5、)已空，將它從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

6、) G是弦圖，且G是伴相似圖( parability 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

7、, C2, Ck是滿足(3)的一個序列區間圖的判定區間圖的判定定理：設G是弦圖，M是G的一個極大團，則存在i，M = Vi Pred(Vi) 定理：ViPredVi是極大團，當且僅當對Vi的任何后繼Vj，至少有一個Vi的前驅不是Vj的前驅。區間圖的判定連續1性質(consecutive ones property, COP or C1P)POJ2790：判斷一個矩陣是否具有C1PAnm ，aij = 1 Vi Cj01010 01000 10101 10100 00011 00101 區間圖的判定N = 4S1=2, 3,S2=3, 4,區間圖的判定PQ-tree 區間圖的判定pertinen

8、t-root區間圖的判定L1當前節點是葉子標記為full區間圖的判定P1當前節點是P-node,子節點都是full標記為full區間圖的判定P2P-node,pertinent-root,full + empty增加新的P-node作為full子節點的父節點及當前節點的子節點(如果只有1個full子節點則不增加新的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區間圖的判定Q3