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

區(qū)間圖弦圖和完美圖第1頁，共46頁，2023年，2月20日，星期五內(nèi)容介紹在本講中將主要介紹區(qū)間圖(intervalgraph)區(qū)間圖上的色數(shù)(chromaticnumber)和最大團問題(maximumclique)完美消除序列(perfecteliminationorder)弦圖(chordalgraph)及其判定區(qū)間圖的判定完美圖(perfectgraph)第2頁，共46頁，2023年，2月20日，星期五區(qū)間圖–POJ1083[POJ1083]MovingTables一個公司有400個房間，布局如上圖所示。編號為奇數(shù)的房間在背面，編號為偶數(shù)的房間在南面，中間被一條走廊隔開?，F(xiàn)在公司要將某些桌子從一個房間移動到另一個房間。走廊很窄，如果兩張桌子需要經(jīng)過同一段走廊的話，那么它們不能同時移動。每移動一張桌子需要10分鐘。問最少需要多久才能將所有桌子移動完畢。第3頁，共46頁，2023年，2月20日，星期五區(qū)間圖–POJ1083Moving：2->45->1412->106->124615141210求一般圖的色數(shù)是NP難問題！第4頁，共46頁，2023年，2月20日，星期五區(qū)間圖–定義一個區(qū)間是有兩個端點的線段，端點可以是開的或閉的。給定一些區(qū)間，可以定義一個相交圖。定義1：給定一些區(qū)間，定義一個相交圖的每個頂點v代表一個區(qū)間Iv,頂點(v,w)間有邊，當(dāng)且僅當(dāng)Iv交Iw非空。定義2：一個圖G是區(qū)間圖，如果它是若干區(qū)間的相交圖。第5頁，共46頁，2023年，2月20日，星期五區(qū)間圖–例區(qū)間圖的例子不是區(qū)間圖的例子第6頁，共46頁，2023年，2月20日，星期五區(qū)間圖–頂點排序定理1：開區(qū)間、閉區(qū)間、半開閉區(qū)間對應(yīng)的區(qū)間圖是等價的。證明思路：由于區(qū)間在連續(xù)的實數(shù)軸上，我們可以對區(qū)間做小量伸縮而不影響相交情況第7頁，共46頁，2023年，2月20日，星期五區(qū)間圖–頂點排序推論1：任何區(qū)間圖G都存在一個沒有重點的區(qū)間表示于是我們可以將G的頂點按其代表區(qū)間的左端點排序，稱之為區(qū)間圖G頂點的自然排序第8頁，共46頁，2023年，2月20日，星期五區(qū)間圖–頂點排序24165141210v2v1v3v4第9頁，共46頁，2023年，2月20日，星期五區(qū)間圖–頂點排序定義2：Pred(Vi)={Vj|(Vi,Vj)∈E∧j<i}為頂點Vi的前驅(qū){Vi}∪Pred(Vi)是一個團第10頁，共46頁，2023年，2月20日，星期五區(qū)間圖–最小染色算法令v1,v2..vn為頂點的一個自然排序，一下算法得到區(qū)間圖G的一個最小染色第11頁，共46頁，2023年，2月20日，星期五完美消除序列定義：一個頂點序列{V1..Vn}如果對任意i滿足Pred（Vi）是一個團，那么這種序列稱為完美消除序列。最大團最大獨立集最小覆蓋最小團覆蓋……第12頁，共46頁，2023年，2月20日，星期五弦圖定義：如果一個圖的任何誘導(dǎo)子圖都不是K階環(huán)（K>=4），那么該圖稱為弦圖第13頁，共46頁，2023年，2月20日，星期五弦圖與完美消除序列定理：如果一個圖G具有完美消除序列，則G是弦圖。第14頁，共46頁，2023年，2月20日，星期五弦圖與完美消除序列定理：圖G是弦圖，當(dāng)且僅當(dāng)G具有完美消除序列第15頁，共46頁，2023年，2月20日，星期五弦圖與完美消除序列定義：如果與頂點V相鄰的所有頂點構(gòu)成一個團，則V稱為單純點引理1：任何弦圖G具有至少一個單純點。如果G不是完全圖，那么它至少具有兩個不相鄰的單純點。引理2：弦圖的任何誘導(dǎo)子圖都是弦圖。第16頁，共46頁，2023年，2月20日，星期五弦圖與完美消除序列引理1：任何弦圖G具有至少一個單純點。如果G不是完全圖，那么它至少具有兩個不相鄰的單純點。第17頁，共46頁，2023年，2月20日，星期五弦圖與完美消除序列最大勢算法(MCS)字典序廣度優(yōu)先搜索(LexicographicalBFS)第18頁，共46頁，2023年，2月20日，星期五弦圖與完美消除序列LexBFS{A,D,C,B,E,F,G,H,J,K,I,L}第19頁，共46頁，2023年，2月20日，星期五弦圖的判定LexBFS–O(n+m)1.令Vi是第一個桶中的第一個元素(顯然Vi是目前標(biāo)號最大的一個頂點)。2.將Vi從桶S(L(Vi))中刪去。3.如果S(L(Vi))已空，將它從Q中刪去。4.對于每個Vi的相鄰點W：5.如果W仍在Q中(W尚未選擇，必須更新它的標(biāo)號和在Q中的位置)6.找到S(L(W))以及它在Q中的位置。7.尋找Q中S(L(W))上一個桶。8.如果這樣的桶不存在,或它不是S(L(W)〇i)9.在Q中的當(dāng)前位置建立一個桶S(L(W)〇i)10.將W從S(L(W))中取出并加入S(L(W)〇i)中11.如果S(L(W))已空，將它刪除。12.將L(W)更新為L(W)〇i。第20頁，共46頁，2023年，2月20日，星期五弦圖的判定檢驗–O(n+m)第21頁，共46頁，2023年，2月20日，星期五弦圖的判定ZOJ–FishingNet判斷一個圖是不是弦圖第22頁，共46頁，2023年，2月20日，星期五再談區(qū)間圖定理：以下命題是等價的：(1)G是區(qū)間圖(2)G是弦圖，且G是伴相似圖(co-comparabilitygraph)。(3)G的極大團可以連續(xù)地編號。即我們可以將它們排為C1..Ck，滿足對于任何v∈V，序列{j|j∈{1..k}，v∈Cj}是連續(xù)整數(shù)集。第23頁，共46頁，2023年，2月20日，星期五再談區(qū)間圖定義：一個能夠無環(huán)且具有傳遞性地定向的無向圖G稱為相似圖。定理：(1)->(2)定理：(3)->(1)I(V)=[Min{i|V∈Ci}，Max{i|V∈Ci}]第24頁，共46頁，2023年，2月20日，星期五再談區(qū)間圖定理(2)->(3)令G’是G補圖經(jīng)過無環(huán)傳遞定向后的有向圖。構(gòu)造有向圖H.V(H)=C,<C1,C2>∈E(H)存在x∈C1,y∈C2且<x,y>∈G’第25頁，共46頁，2023年，2月20日，星期五再談區(qū)間圖定理：H是傳遞的第26頁，共46頁，2023年，2月20日，星期五再談區(qū)間圖定理：H是無環(huán)的第27頁，共46頁，2023年，2月20日，星期五再談區(qū)間圖定理：H的一個拓撲排序C1,C2,…Ck是滿足(3)的一個序列第28頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定第29頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定定理：設(shè)G是弦圖，M是G的一個極大團，則存在i，M={Vi}∪Pred(Vi)定理：{Vi}∪Pred{Vi}是極大團，當(dāng)且僅當(dāng)對Vi的任何后繼Vj，至少有一個Vi的前驅(qū)不是Vj的前驅(qū)。第30頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定連續(xù)1性質(zhì)(consecutiveonesproperty,COPorC1P)POJ2790：判斷一個矩陣是否具有C1PAnm，aij=1Vi∈Cj01010

01000

10101

10100

00011

00101第31頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定N=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,4><3,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>}第32頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定PQ-tree/2008/11/pq-tree-algorithm-and-consecutive-ones.htmlhttp://www.jharris.ca/portfolio/code/pqtree/PQTree.html第33頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定pertinent-root第34頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定L1當(dāng)前節(jié)點是葉子標(biāo)記為full第35頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定P1當(dāng)前節(jié)點是P-node,子節(jié)點都是full標(biāo)記為full第36頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定P2P-node,pertinent-root,full+empty增加新的P-node作為full子節(jié)點的父節(jié)點及當(dāng)前節(jié)點的子節(jié)點(如果只有1個full子節(jié)點則不增加新的P-node)第37頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定P3P-node,notpertinent-root,full+empty當(dāng)前節(jié)點標(biāo)記為partialQ-node,增加新的P-node作為full子節(jié)點的父節(jié)點及當(dāng)前節(jié)點的子節(jié)點,增加新的P-node作為empty子節(jié)點的父節(jié)點及當(dāng)前節(jié)點的子節(jié)點,第38頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定P4P-node,pertinent-root,1partial+full+empty第39頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定P5P-node,notpertinent-root,1partial+full+empty第40頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定P6P-node,pertinent-root,2partial+full+empty第41頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定Q1Q-node,allfull第42頁，共46頁，2023年，2月20日，星期五區(qū)間圖的判定Q2Q-node,0/1partial+連續(xù)full+empty第43頁，共46頁，2023年，2月20日，星期