Turán-tétel

1. Sablon:Gráf A Turán-tétel vagy Turán-féle gráftétel meghatározza, hogy legfeljebb hány éle lehet egy (teljes 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.

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=kq+r$, ahol $0\le r<k$ és egy n pontú gráfban nincs $K_{k+1}$, akkor az élek e számára

$e\le \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.

---

Turán-tétel

A **Turán-tétel** a gráfelmélet egyik alapvető eredménye, amely megadja, hogy egy adott számú csúcsú, hurokmentes gráf maximálisan hány élt tartalmazhat úgy, hogy az adott gráfban ne legyen adott méretű teljes részgráf.

A tétel megfogalmazása

Legyen $G=(V,E)$ egy $n$ csúcsú egyszerű gráf, amelyben nincs $K_r$, azaz $r$ csúcsú teljes részgráf. Ekkor:

$|E|\le (1-\frac{1}{r-1})\frac{n^2}{2},$

és az egyenlőség pontosan akkor teljesül, ha $G$ az úgynevezett **Turán-gráf**, amely az $n$ csúcsokat $r-1$ majdnem egyenlő méretű partícióra osztja, és az összes él az egyes partíciók között fut.

Magyarázat

A tétel megadja, hogy egy $K_r$-mentes gráf maximális él-száma attól függ, hogy hány csúcsa van, és milyen méretű teljes részgráfot (klikket) akarunk elkerülni.

• **Teljes gráf:** Egy gráf teljes, ha minden csúcs között fut él.
• **Teljes részgráf:** Egy részgráf teljes, ha a részgráf csúcsai között minden csúcs össze van kötve.
• **Turán-gráf:** Egy speciális bipartit vagy több-partit gráf, amelyben a csúcsok egyenletesen vannak partíciókba osztva, és minden él különböző partíciók között fut.

Példa

Legyen $n=6$, és keressük annak a gráfnak a maximális él-számát, amely nem tartalmaz $K_3$-at (három csúcsból álló teljes gráf).

1. A Turán-tétel szerint $r=3$, ezért:

  $|E|\le (1-\frac{1}{3-1})\frac{6^2}{2}=\frac{2}{3}\cdot \frac{36}{2}=12.$

2. Az egyenlőség elérése érdekében a Turán-gráf egy $K_3$-mentes, 6 csúcsú gráf, amely két partícióra osztja a csúcsokat, például $V_1=\{1,2,3\}$ és $V_2=\{4,5,6\}$. Az élek csak $V_1$ és $V_2$ között futnak.

A maximális él-szám tehát 12, és a gráf egy 2-partit gráf.

Következmények

A Turán-tételnek fontos szerepe van a gráfelméletben és a kombinatorikában, különösen az extremális gráfelméletben:

• Megadja a maximális él-számot, ha bizonyos részgráfok hiányát akarjuk biztosítani.
• Hasznos a Ramsey-elméletben, amely azzal foglalkozik, hogy bizonyos részgráfok jelenléte vagy hiánya miként függ a gráf paramétereitől.
• Szoros kapcsolatban áll az Erdős-Stone-tétellel, amely általánosítja a Turán-tételt.

További megjegyzések

• Ha $r=2$, akkor a Turán-tétel egyszerűen azt adja meg, hogy egy hurokmentes gráf maximális él-száma $\frac{n^2}{2}$, amely a teljes gráf.
• A Turán-tétel általánosítása magasabb dimenziójú struktúrákra is alkalmazható (pl. hipergráfok).
• Az extremális gráfelmélet egyik legfontosabb eredménye, amely segít meghatározni bizonyos gráftulajdonságok szélsőértékeit.

Sablon:-ford- Sablon:Trans-top

• Sablon:En: Sablon:T