Turán-tétel

• IPA:

Turán-tétel

1. (matematika, gráfelmélet) 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.^[1]

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

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

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

${\displaystyle 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 ${\displaystyle A_{1},\dots ,A_{k}}$ halmazból áll, ahol ${\displaystyle |A_{1}|=\cdots =|A_{r}|=q+1}$, ${\displaystyle |A_{r+1}|=\cdots =|A_{k}|=q}$, két pontot pontosan akkor kötünk össze, ha különböző osztályokban vannak.

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.

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

${\displaystyle |E|\leq \left(1-{\frac {1}{r-1}}\right){\frac {n^{2}}{2}},}$

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

A tétel megadja, hogy egy ${\displaystyle 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.

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

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

  ${\displaystyle |E|\leq \left(1-{\frac {1}{3-1}}\right){\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 ${\displaystyle K_{3}}$-mentes, 6 csúcsú gráf, amely két partícióra osztja a csúcsokat, például ${\displaystyle V_{1}=\{1,2,3\}}$ és ${\displaystyle V_{2}=\{4,5,6\}}$. Az élek csak ${\displaystyle V_{1}}$ és ${\displaystyle V_{2}}$ között futnak.

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

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.

• Ha ${\displaystyle r=2}$, akkor a Turán-tétel egyszerűen azt adja meg, hogy egy hurokmentes gráf maximális él-száma ${\displaystyle {\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.

• Turán-tétel - Értelmező szótár (MEK)
• Turán-tétel - Etimológiai szótár (UMIL)
• Turán-tétel - Szótár.net (hu-hu)
• Turán-tétel - DeepL (hu-de)
• Turán-tétel - Яндекс (hu-ru)
• Turán-tétel - Google (hu-en)
• Turán-tétel - Helyesírási szótár (MTA)
• Turán-tétel - Wikidata
• Turán-tétel - Wikipédia (magyar)