Turán-tétel

Magyar

Kiejtés

• IPA: [ ˈturaːnteːtɛl]

Főnév

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.

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\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.

---

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|\leq \left(1-{\frac {1}{r-1}}\right){\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|\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 $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.

Fordítások

Tartalom

angol: Turán's theorem (en)

További információk

• 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)