穩定性定理

穩定性定理(stability theorems)圖論的重要定理之一描述極圖偏離程度的定理一般指第一穩定性定理和第二穩定性定理.第一穩定性定理如下:設丫是一禁用圖類，其次色數為p，對於任意。>0,存在}E>0和正整數n#>0，滿足條件:若n階圖Gn不含任何LEA，及n>nE，且G的邊數大於ex(n,cue)-}Enz，則G、可由T,，改變最多enz條邊得到.第二穩定性定理如下:設丫是禁用圖類，次色數為p，分解為fc,k>O,G"EEx(n,}),S}}},5，為它的最優劃分，G一CS>，若e(G")>ex(n，丫)一k·ex(n,}c)，則有下面的結論:

1.G”可由X(G刪除O(ex(n,}c))條邊得到.

2. a (G;)=O(ex(n，產))十O(n)， }V <G川=<n /p)+O(,}ex(n,}c)).

3.對任意常數。>0,G，中滿足a(v)>cn的頂點數僅為O(1)，滿足b(v)>cn的頂點數僅為

O(ex(n,fc)/n)+O(1).

4.設LE },川=r，若A為S中滿足b<v)鎮}n/2pr]的頂點v的集合，則圖<A>不含L.

以上敍述中最優劃分是指失去邊最少的劃分.Q (v)和b(v)分別表示頂點v處失去和增加的邊數.X表示聯圖的運算符號.第二穩定性定理以極圖偏離XG的程度描述了極圖的穩定性. ^[1]