Turán-féle gráftétel

A Wikipédiából, a szabad enciklopédiából.

A Turán-féle gráftétel meghatározza, hogy legfeljebb hány éle lehet egy (véges) gráfnak, amely nem tartalmaz adott nagyságú teljes gráfot. Turán Pál 1941-ben publikálta tételét, ami a gráfelmélet egy jelentős fejezetét, az extremális gráfelméletet indította el.

Tartalomjegyzék

1 A tétel
2 A háromszögnélküli eset
- 2.1 Első bizonyítás
- 2.2 Második bizonyítás
3 Az általános eset bizonyítása

[szerkesztés] A tétel

Egyszerűbb formájában a tétel a következőt mondja: ha egy n szögpontú gráfban nincs $K k + 1$ (teljes k+1-es) akkor éleinek száma legfeljebb

$\frac{k-1}{2k}n^2.$

A tétel teljes formája szerint, ha $n = k q + r$ , ahol $0\leq r<k$ és egy n pontú gráfban nincs $K k + 1$ , akkor az élek e számára

$e\leq \frac{k-1}{2k}n^2-\frac{r(k-r)}{2k}$

teljesül. Ez minden n-re pontos, egyenlőség egyetlen gráfra, a T(n,k) Turán-gráfra teljesül: ez k közös elem nélküli $A_1,\dots,A_k$ halmazból áll, ahol $|A_1|=\cdots=|A_r|=q+1$ , $|A_{r+1}|=\cdots=|A_k|=q$ , két pontot pontosan akkor kötünk össze, ha különböző osztályokban vannak.

[szerkesztés] A háromszögnélküli eset

Ebben a speciális esetben (amit Mantel már 1907-ben igazolt) azt kell belátnunk, hogy ha egy n szögpontú gráfban nincs háromszög, akkor az élek e számára $e\leq \frac{n^2}{4}$ teljesül

[szerkesztés] Első bizonyítás

Legyenek a csúcsok $v_1,\dots,v_n$ . Tegyük fel, hogy a $v i$ és a $v j$ csúcsok össze vannak kötve. A további $n - 2$ pont egyike sem lehet mindkettővel összekötve. Ezen $n - 2$ pontból $d (v i) - 1$ és $d (v j) - 1$ van összekötve $v i$ -vel, illetve $v j$ -vel (ahol $d (v)$ a v pont foka). Mivel egyik sem lehet mindkettővel összekötve, kapjuk, hogy

$(d(v_i)-1)+(d(v_j)-1)\leq n-2$

azaz

$d(v_i)+d(v_j)\leq n$

Ezt minden összekötött pontpárra összeadva a jobboldal en lesz, a baloldalban pedig minden $d (v i)$ tag annyiszor szerepel, ahány élben $v i$ van, azaz $d (v i)$ -szor. Tehát

$d(v_1)^2+\cdots+d(v_n)^2\leq en$

adódik.

A számtani és négyzetes közép közötti egyenlőtlenséget felhasználva

$\left(\frac{d(v_1)+\cdots+d(v_n)}{n}\right)^2\leq\frac{d(v_1)^2+\cdots+d(v_n)^2}{n}.$

Mivel $d(v_1)+\cdots+d(v_n)=2e$ , a fenti egyenlőtlenséget így alakíthatjuk:

$\left(\frac{2e}{n}\right)^2\leq e$

ami átrendezve éppen a bizonyítandó állítás.

[szerkesztés] Második bizonyítás

Legyen a legnagyobb független (élnélküli) ponthalmaz elemszáma k és legyen A egy k-elemű független halmaz. Jelöljük B-vel A komplementerét. Mivel a gráfban nincs háromszög, minden pont szomszédainak halmaza független, tehát legfeljebb k elemű. Továbbá minden élnek egyik, esetleg mindkét végpontja B-beli (mert A független), így az élek e számára a következőt kapjuk:

$e\leq \sum_{v\in B}d(v)\leq |B|k=(n-k)k\leq \left(\frac{n}{2}\right)^2,$

az utolsó lépésben felhasználva a számtani és mértani közép közötti egyenlőtlenséget.

[szerkesztés] Az általános eset bizonyítása

A tételt q-ra indukcióval igazoljuk. Ha q=0, akkor tehát a gráfnak r<k csúcsa van, semmiképpen sem lehet benne teljes (k+1)-szög, az élek maximális száma így

${{r}\choose{2}}=\frac{k-1}{2k}r^2-\frac{r(k-r)}{2k},$

amint azt kiszorzással láthatjuk.

Tegyük fel, hogy q>0 és adott egy n szögpontú és maximális élszámú $K k + 1$ -et nem tartalmazó gráf. Ebben mindenképpen van teljes k-as, különben egy élt még hozzá tudnánk adni. Legyen A egy k elemű teljes ponthalmaz, B pedig a maradék pontok halmaza. Nyilván B elemszáma n-k. Jelölje a,b,c rendre az A-ban, B-ben, illetve A és B között futó élek számát. Nyilván $e = a + b + c$ . Mivel A teljes gráf,

$a={{k}\choose{2}}.$

Az indukció miatt azt is tudjuk, hogy

$b\leq \frac{k-1}{2k}(n-k)^2-\frac{r(k-r)}{2k}.$

Egyetlen B-beli pont sem lehet összekötve minden A-belivel, hiszen ekkor lenne egy teljes (k+1)-es. Azaz minden B-beli pontból legfeljebb k-1 él megy A-ba, így minden pontra összeszámolva adódik $c \leq (n-k)(k-1)$ .

Összeadva adódik

${{k}\choose{2}}+\frac{k-1}{2k}(n-k)^2-\frac{r(k-r)}{2k}+(n-k)(k-1)$

ami, mint kiszorzással látható, azonos a következővel:

$\frac{k-1}{2k}n^2-\frac{r(k-r)}{2k}.$

Be kell még látnunk, hogy egyenlőség csak a Turán-gráf esetén teljesül. Ha egyenlőség van, akkor b és c esetén is egyenlőségnek kell teljesülnie. Azaz minden B-beli csúcs k-1 A-beli csúccsal van összekötve és (az indukció miatt) B a T(n-k,k) Turán-gráf. B felbomlik a majdnem egyenlő nagyságú $B_1,\dots,B_k$ halmazokra és pontosan a különböző halmazokban levő csúcsok vannak összekötve. Két különböző $B i$ -ben levő csúcs nem lehet ugyanazzal a k-1 A-beli csúccsal összekötve, mert ekkor teljes k+1-est kapnánk. Mivel A-nak pontosan k darab k-1 elemű részhalmaza van, csak az lehet, ha minden -beli csúcs ugyanabba az A-beli csúcsba nincs bekötve, és ez különböző i-re különböző, ezért A elemeit felsorolhatjuk $a_1,\dots,a_k$ -ként, hogy $B i$ elemei potosan $a i$ -be nincsenek bekötve. De ezzel azt kapjuk, hogy gráfunk a $T (n, k)$ Turán-gráf az $B_1\cup\{a_1\},\dots,B_k\cup\{a_k\}$ osztályokkal.