弦圖與區間圖

原來想把論文裡面所有沒證的東西都證一遍，結果發現我太弱證不了【捂臉熊】那就把一些結論記一下吧QAQ以後有什麼興趣的話再來補證明

一些定義什麼的自行腦補吧

1.對任意的一張圖來說，團數<=色數，最大獨立集數<=最小團覆寫數。當圖是弦圖的時候這兩個式子都取到了等号。　　

2.一張圖是弦圖當且僅當它有一個完美消除序列。

3.最大勢算法（MCS）求一張弦圖的完美消除序列。從n到1的順序給每個點标号，設label[i]表示i與多少個已經标号的節點标号。那麼每次選擇label[i]最大點進行标号。

   mlogn的算法隻要維護一個堆即可。O（n+m）可以考慮給每個label[i]=j的j挂連結清單表示誰的label是j。

4.判斷一個序列是否為完美消除序列。

   設v[i+1……n]中與v[i]相鄰的從前往後依次是v[j1]v[j2]。。。v[jk]隻要判斷v[j1]與其他的節點是否相鄰即可。（正确性顯然）

   複雜度O（n+m）我們可以考慮從1到n判斷，每次就給 i 對應的j1挂連結清單表示j1需要與誰相鄰，然後複雜度應該均攤是O（n+m）

5.設N（i）表示與i節點相鄰的且在完美消除序列中處于i之後的節點集合。根據定義可知i∪N（i）為一個團。

   那麼最大團一定是i∪N（i）的形式。證明可以把最大團的最前面那個點拎出來。

   同理可以證明所有的團都是i∪N（i）或者是i∪N（i）的一個子集。

6.弦圖的最大點獨立集可以把完美消除序列求出來後從前往後能選就選。（為什麼？）

7.求出最大點獨立集之後取最大點獨立集中的每個點i∪N（i）的團即為一個最小團覆寫。（這裡的N（i）的定義還和原來的相同？）

8.完美圖指一個圖的任意一個誘導子圖都滿足 團數=色數，而伴完美圖指任何一個誘導子圖都滿足  最大點獨立集=最小團覆寫 

   完美圖=伴完美圖。弦圖是完美圖。

9.區間圖是弦圖。

10.給定n個區間，要求選擇最多的區間 使得區間不互相重疊。其實就是區間圖的最大點獨立集。

11.有n個積木，高度均為1，第i個積木的寬度範圍為[Li, Ri]，選擇一個積木的下落順序使得最後積木總高度盡可能小。其實就是區間圖的最小染色數。

12.區間圖的一個完美消除序列可以把所有的區間按照右端點從小到大排序而得到。

後面就棄療了【捂臉熊】