tioj 1210 圖論 之 簡單圖測試

先想一下再來討論接下來的內容

其實題目就是給一個 di 的集合，問可否形成一簡單圖。

1. 對任意圖 sum of di 必為二的倍數（理由過於簡單自己想）
2. 對任意簡單圖，任一 di 必 <= ( n-1 ) 。

接下來的討論都是建構在以上兩假設成立的情況。


有兩種判斷方式

第一個是Erdős–Gallai theorem ( Online proof <- 較嚴謹?! )

定理：
在 di 有大到小排列過後，此序列為簡單圖
若且為若對於任意的 1<= k <= n-1，sum(1~k) di <= k(k-1) + sum(k+1~n) min( di, k )
證明：
（->）k(k-1)+sum(k+1~n) min( di, k ) 為最大上限，前項代表的就是前面k個點，每個都互相連接，後項則為除那些k點外的點與此k點最大的連結數量（min的原因是點數(k)有限）。
（<-）我們用反證法，若此序列無法畫成簡單圖，則一定可以找到某一k使得sum(1~k) > k(k-1) + sum(k+1~n) min( di, k )。
至於為什麼要排序過的原因其實是，此式子最最基本的想法應該是要判斷每一種分法，但是若有一種分法，他左邊的某一元素小於右邊的，則你將他們對調，會使得此不等是更不容易成立，故直接 O(n) 看過排序後的序列，不但更省時而且是對的。

我覺得我的證明比他的好XD


第二個是 Havel 定理

定理：
有一個度序列 x = {d1, d2, d3, d4 ... } 且d1>=d2>=d3>=...，若且為若此度序列可畫為簡單圖，則另一度序列x' = { d2-1, d3-1, d4-1, ... d(d1)-1, d(d1+1), ... dn }可畫為簡單圖。
證明：
（<-）若 x' 為可圖序列，加上一點d1，並與其他的 d1 個點相連，則此圖仍為簡單圖。
（->）若 G 中存在 ( v1, v2 ) & ( v1, v3 ) & ( v1, v4 ) ...，將這些邊都去掉並拔掉 v1 後，不會影響他的簡單圖性質。如果G不如上述，亦即存在某( v1, vi )不屬於G，但( v1, vj )屬於G（其中 i<j）
因為 di >= dj 故必定可以找到一個點 k ，( vi, vk ) 屬於G，但( vj, vk ) 不屬於G，即可將邊做一點調換，但不改變度序列，即可回到上述的情況。

O( n ) 算法： http://codepad.org/LoHkJa4K