托蘭定理

圖論中, 托蘭定理是 K_(r+1)-free 圖中邊數的結果。

通過將一組頂點集劃分為大小相等或幾乎相等的r個部分,並在兩個頂點屬於兩個不同子集的情況下,通過邊連線兩個頂點,可以形成不包含任何(r+1)個點團的n點圖 部分。我們稱產生的圖為托蘭圖 T(n,r)。 托蘭定理指出,托蘭圖在所有K_(r+1)-free的n點圖中具有最多的邊數。

托蘭圖是由匈牙利數學家帕爾托蘭(PálTurán)於1941年首次描述和研究的,儘管曼特爾(Mantel)早在1907年就指出了該定理的一個特例。

基本介紹

  • 中文名:托蘭定理
  • 外文名:Turán's theorem
  • 別名:圖蘭定理、土倫定理
  • 領域圖論
  • 提出人:帕爾托蘭
  • 提出時間:1941年
  • 適用學科組合數學
定理描述,證明,特殊情形,

定理描述

令G為具有n個頂點的任何圖,使得G為K_(r+1)-free。 那么G中的邊數最多為
等效表達如下:
在沒有(r+1)點團的n個頂點的簡單圖中,T(n,r)的邊數最大。

證明

令G為不具有(r+1)點團且具有最大邊數的n頂點的簡單圖。
概述:我們在證明之前進行簡要概述,以下的證明包括兩個關於G的聲明。
第一個聲明是G必須是完全r部圖(儘管下面會更詳細地說明)。換句話說,我們可以將頂點集劃分為r個子集S_1, S_2, … , S_r, 這樣,如果兩個頂點在不同的集合S_i 和 S_j 中,則它們之間有一條邊,但是如果它們是在同一組中,那么它們之間就沒有任何邊。
第二個聲明是這些集合S_i 的大小彼此相差最多1。例如,如果我們要在23個頂點上繪製圖,而且有最多的邊但不包含三角形,則可以對這些頂點進行劃分分為集合 S_1 和 S_2,其中 | S_1 | = 12, | S_2 | = 11。我們將兩組之間的所有邊相加,因此圖形將具有11 * 12 = 132條邊。這與定理匹配,該定理說G最多具有
條邊。
下面證明兩個聲明。
聲明1:圖G不包含任何三個頂點u,v,w,使得G包含邊uv,但不包含邊uw和vw。 (此聲明等同於關係x~y,如果x與y不相關,則為等價關係。〜總是自反且對稱的,但僅在特殊情況下,它是可傳遞的。~當我們具有u,v,w與u~w和w~v而沒有u~v)。
假設聲明是錯誤的。構造一個不包含(r+1)點團但具有比G多的邊的新n頂點簡單圖G',如下所示:
情況1:
或者
假設
,刪除頂點w並創建頂點u的複製(所有鄰居都與u相同);稱它為u'。新圖中的任何點團最多在{u,u'}中包含一個頂點。因此,此新圖不包含任何(r+1)點團。但是,它包含更多的邊:
情況2:
刪除頂點u和v並創建頂點w的兩個新複製。同樣,新圖不包含任何(r +1)點團。但是,它包含更多的邊:
這證明了聲明1。
這種說法證明,可以根據非鄰居將G的頂點劃分為等價類。也就是說,如果兩個頂點不相鄰,則它們在同一個等價類中。這意味著G是一個完全多部圖(其中部分是等價類)。
聲明2:如果部分的大小相差最多1個,則完全k部圖中的邊數將最大化。
如果G是具有A和B以及
的完全k分圖,則可以通過將頂點從A移動到B來增加G中的邊數。通過將頂點從A移動到B,圖將失去 |B| 邊數,但獲得 |A|-1 條邊。因此,它至少獲得了
條邊。這證明了聲明2。
該證明表明Turan圖具有最大數量的邊。此外,證明表明只有托蘭圖是具有最大邊數的圖。

特殊情形

下面對於托蘭定理 r=2 的著名情形給出證明。該情形也稱作Mantel's theorem。
定理表述
在不存在三邊迴路的n頂點圖中,邊數最大為
換句話說,必須刪除K_n中幾乎一半的邊才能獲得無三角圖。
Mantel定理的加強
任何至少具有
條邊的哈密頓圖必須是完整的二分圖K(n/2),(n/2)或必須是全圈形的:不僅包含三角形,而且還必須包含所有其他可能長度到頂點數為止的迴路(Bondy 1971)。
Mantel定理的另一項加強說明,每個n頂點圖的邊最多可以被
點團覆蓋,它們可以是邊或三角形。 作為推論,相交數最多為
(Erdős,Goodman&Pósa1966)。
Mantel定理的證明
設A為n個點中,向外連線最多的點,設它向外連k條線,則與A相連的點之間不允許連線
而剩餘(n-1-k)中的任意一點不可能向外連線數大於k,設這些點連線總數為y,則有
時,y是整數,所以y的最大值為
所以

相關詞條

熱門詞條

聯絡我們