Turanova věta

Turánova věta odpovídá na otázku maximálního počtu hran v grafu bez úplného n-vertexového podgrafu .

Problém zakázaného podgrafu poprvé položil maďarský matematik Pal Turan v roce 1941 .

Formulace

Notace

Označte úplným n-vertexovým grafem. $K_n$

Graf s vrcholy definujeme následovně. Rozdělme všechny vrcholy do „téměř stejných“ skupin (tzn. vezměme skupiny po vrcholech a skupiny po vrcholech, pokud se zbytkem ) a spojíme všechny dvojice vrcholů z různých skupin hranami. Tak získáme -partitní graf. $T_{n}(v)$ $proti$ $n-1$ $r$ $m+1$ $n-1-r$ $m$ $v:(n-1)=m$ $r$ $(n-1)$

Budeme označovat maximálním počtem hran, které může mít graf s vrcholy, které neobsahují podgraf izomorfní k . $ex(v,n)$ $proti$ $K_n$

Věta

Ze všech grafů na vrcholech, které neobsahují podgraf , má graf maximální počet hran . Jestliže , kde je zbytek po dělení , pak se toto maximum rovná $proti$ $K_n$ $T_{n}(v)$ $v=m(n-1)+r$ $r$ $proti$ $n-1$

ex(v,n)={\frac {(n-2)(v^{2}-r^{2})}{2n-2}}+{\frac {r(r-1)}{2 }}

Poznámky

Pomocí hlavního vzorce lze napsat kratší: $n\leq 8$ $ex(v,n)=\left[v^{2}\cdot {\frac {n-2}{2n-2}}\right]$ .

Důkaz

Důkaz lze provést např. matematickou indukcí počtu vrcholů v grafu . $proti$

Zavádíme indukci počtu vrcholů v úplném podgrafu. $n$

Základna . Důkaz: Zavedeme indukci počtu vrcholů. $n=3$
- Základna . Pro tyto případy je odhad zřejmý. $n=1,2$
- Krok: Nechte dokázat pro . Dokažme pro . Pokud v grafu nejsou žádné hrany, pak je vše dokázáno. V opačném případě vyberte hranu. Všimněte si, že ze zbývajících vrcholů grafu nejde k této hraně více než jedna hrana (jinak je zde trojúhelník), tyto hrany nejsou více než . Pro zbytek grafu aplikujeme indukční hypotézu. Od toho celkový počet hran není větší než . Což bylo požadováno. $k$ $k+2$ $\Šipka doprava$ $k$ ${\frac {k^{2}-r^{2}}{4}}+k+1={\frac {(k+2)^{2}-r^{2}}{4 }}$
Základ je osvědčený.

Krok. Ať je to pravda, my to dokážeme . Zavádíme indukci. Základna . Pro tyto případy je tvrzení zřejmé. Krok. Ať je to pravda, my to dokážeme . Pokud graf nemá kompletní graf na vrcholech, použijeme předchozí krok (samozřejmě bude lepší odhad). V opačném případě jej vybereme. Z každého z ostatních vrcholů na něj nejde více než hran, tedy ne více než . Celkový počet hran v grafu tedy nepřesahuje $n-1$ $n$ $k=1,2,\ldots ,n-1$ $k$ $k+n-1$ $n-1$ $n-2$ $k\cdot (n-2)$

( n − 2 ) ( k 2 − r 2 ) 2 n − 2 + ( n − jeden ) ( n − 2 ) 2 + k ⋅ ( n − 2 ) + r ⋅ ( r − jeden ) 2 = ( n − 2 ) ( ( k + n − jeden ) 2 − r 2 ) 2 n − 2 + r ⋅ ( r − jeden ) 2 {\displaystyle {\frac {(n-2)(k^{2}-r^{2})}{2n-2))+{\frac {(n-1)(n-2)}{2 }}+k\cdot (n-2)+{\frac {r\cdot (r-1)}{2}}={\frac {(n-2)((k+n-1)^{2 }-r^{2})}{2n-2}}+{\frac {r\cdot (r-1)}{2}}} ${\frac {(n-2)(k^{2}-r^{2})}{2n-2))+{\frac {(n-1)(n-2)}{2 }}+k\cdot (n-2)+{\frac {r\cdot (r-1)}{2}}={\frac {(n-2)((k+n-1)^{2 }-r^{2})}{2n-2}}+{\frac {r\cdot (r-1)}{2}}$ Což bylo požadováno. Krok indukce je dokázán.

Variace a zobecnění

Důkaz Turánova teorému přináší o něco silnější výsledek: pro každý graf , který neobsahuje kopii úplného grafu, existuje -částečný graf se stejnou množinou vrcholů jako se stupněm každého vrcholu alespoň y . $\Gamma$ $K_{n+1}$ $n$ $\gamma'$ $\Gamma$ $\Gamma$

Literatura

"Teorie grafů" O. Ore. 1980
Berge C. Graphs (druhé revidované vydání), North-Holland, Amsterdam-New York-Oxford, 1985.
Lovasz L. Kombinatorické problémy a cvičení, Academiqi Kiado, Budapešť, 1979.

Externí odkazy

Turanova věta ve Slovníku teorie grafů