區(qū)間圖、弦和完美

1、區(qū)間圖、弦圖和完美圖介紹內(nèi)容介紹在本講中將主要介紹區(qū)間圖(interval graph)區(qū)間圖上的色數(shù)(chromatic number)和最大團(tuán)問(wèn)題(maximum clique)完美消除序列(perfect elimination order)弦圖(chordal graph)及其判定區(qū)間圖的判定完美圖(perfect graph)區(qū)間圖 POJ1083POJ1083 Moving Tables一個(gè)公司有400個(gè)房間，布局如上圖所示。編號(hào)為奇數(shù)的房間在背面，編號(hào)為偶數(shù)的房間在南面，中間被一條走廊隔開(kāi)?，F(xiàn)在公司要將某些桌子從一個(gè)房間移動(dòng)到另一個(gè)房間。走廊很窄，如果兩張桌子需要經(jīng)過(guò)同一段走廊的

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

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

4、任何弦圖G具有至少一個(gè)單純點(diǎn)。如果G不是完全圖，那么它至少具有兩個(gè)不相鄰的單純點(diǎn)。引理2：弦圖的任何誘導(dǎo)子圖都是弦圖。弦圖與完美消除序列引理1：任何弦圖G具有至少一個(gè)單純點(diǎn)。如果G不是完全圖，那么它至少具有兩個(gè)不相鄰的單純點(diǎn)。弦圖與完美消除序列最大勢(shì)算法(MCS)字典序廣度優(yōu)先搜索(Lexicographical BFS)弦圖與完美消除序列LexBFSA, D, C, B, E, F, G, H, J, K, I, L弦圖的判定LexBFS O(n + m)1. 令Vi是第一個(gè)桶中的第一個(gè)元素(顯然Vi是目前標(biāo)號(hào)最大的一個(gè)頂點(diǎn))。 2. 將Vi從桶S(L(Vi)中刪去。 3. 如果S(L(Vi

5、)已空，將它從Q中刪去。 4. 對(duì)于每個(gè)Vi的相鄰點(diǎn)W： 5. 如果W仍在Q中(W尚未選擇，必須更新它的標(biāo)號(hào)和在Q中的位置) 6. 找到S(L(W)以及它在Q中的位置。 7. 尋找Q中S(L(W)上一個(gè)桶。 8. 如果這樣的桶不存在,或它不是 S(L(W)i) 9. 在Q中的當(dāng)前位置建立一個(gè)桶S(L(W)i) 10. 將W從S(L(W)中取出并加入S(L(W)i)中 11. 如果S(L(W)已空，將它刪除。 12. 將L(W)更新為L(zhǎng)(W)i 。 弦圖的判定檢驗(yàn) O(n + m)弦圖的判定ZOJ Fishing Net判斷一個(gè)圖是不是弦圖再談區(qū)間圖定理：以下命題是等價(jià)的：(1) G是區(qū)間圖(2

6、) G是弦圖，且G是伴相似圖( parability graph)。(3) G的極大團(tuán)可以連續(xù)地編號(hào)。即我們可以將它們排為C1.Ck，滿(mǎn)足對(duì)于任何vV，序列j| j1.k，vCj是連續(xù)整數(shù)集。再談區(qū)間圖定義：一個(gè)能夠無(wú)環(huán)且具有傳遞性地定向的無(wú)向圖G稱(chēng)為相似圖。定理： (1) - (2)定理： (3) - (1)I(V) = Mini| VCi，Max i| VCi 再談區(qū)間圖定理 (2) - (3)令G是G補(bǔ)圖經(jīng)過(guò)無(wú)環(huán)傳遞定向后的有向圖。構(gòu)造有向圖H. V(H) = C, E(H) 存在xC1,yC2 且G再談區(qū)間圖定理：H是傳遞的再談區(qū)間圖定理：H是無(wú)環(huán)的再談區(qū)間圖定理：H的一個(gè)拓?fù)渑判駽1

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

8、t-root區(qū)間圖的判定L1當(dāng)前節(jié)點(diǎn)是葉子標(biāo)記為full區(qū)間圖的判定P1當(dāng)前節(jié)點(diǎn)是P-node,子節(jié)點(diǎn)都是full標(biāo)記為full區(qū)間圖的判定P2P-node,pertinent-root,full + empty增加新的P-node作為full子節(jié)點(diǎn)的父節(jié)點(diǎn)及當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)(如果只有1個(gè)full子節(jié)點(diǎn)則不增加新的P-node)區(qū)間圖的判定P3P-node,not pertinent-root,full + empty當(dāng)前節(jié)點(diǎn)標(biāo)記為partial Q-node,增加新的P-node作為full子節(jié)點(diǎn)的父節(jié)點(diǎn)及當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn),增加新的P-node作為empty子節(jié)點(diǎn)的父節(jié)點(diǎn)及當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn),區(qū)間圖的判定P4P-node,pertinent-root,1 partial + full + empty區(qū)間圖的判定P5P-node,not pertinent-root,1 partial + full + empty區(qū)間圖的判定P6P-node,pertinent-root,2 partial + full + empty區(qū)間圖的判定Q1Q-node,all full區(qū)間圖的判定Q2Q-node,0/1 partial + 連續(xù)full + empty區(qū)間圖的判定Q3