Hrabě z Turany

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 9. října 2021; ověření vyžaduje 1 úpravu .

hrabě z Turany

Pojmenoval podle	Pal Turan
Vrcholy	n
žebra	$\left\lfloor {\frac {(r-1)n^{2}}{2r}}\right\rfloor$
Poloměr	$\left\{{\begin{array}{ll}\infty &r=1\\2&r\leq n/2\\1&{\text{jinak}}\end{array}}\right.$
Průměr	$\left\{{\begin{array}{ll}\infty &r=1\\1&r=n\\2&{\text{jinak}}\end{array}}\right.$
obvod	$\left\{{\begin{array}{ll}\infty &r=1\vee (n\leq 3\wedge r\leq 2)\\4&r=2\\3&{\text{jinak)) \end{array}}\right.$
Chromatické číslo	r
Označení	= T ( n , r )
Mediální soubory na Wikimedia Commons

Turanův graf T ( n , r ) je graf vzniklý rozkladem n vrcholů na r podmnožin, přičemž velikost je co nejblíže, přičemž vrcholy v tomto grafu jsou spojeny hranou, pokud patří do různých podmnožin. Graf bude mít podmnožiny velikosti a podmnožiny velikosti . Toto je úplný r -partitní graf $(n\,{\bmod {\,}}r)$ $\lceil n/r\rceil$ $r-(n\,{\bmod {\,}}r)$ $\lfloor n/r\rfloor$

K_{\lceil n/r\rceil ,\lceil n/r\rceil ,\ldots ,\lfloor n/r\rfloor ,\lfloor n/r\rfloor }.

Každý vrchol má stupeň buď , nebo . Počet hran je $n-\lceil n/r\rceil$ $n-\lfloor n/r\rfloor$

{\frac {1}{2}}(n^{2}-(n\,{\bmod {\,}}r)\lceil n/r\rceil ^{2}-(r-( n\,{\bmod {\,}}r))\lpodlaží n/r\rpodlaží ^{2})\leq \left(1-{\frac {1}{r}}\right){\frac { n^{2}}{2}}.

Graf je regulární , jestliže n je dělitelné r .

Turanova věta

Turanovy grafy jsou pojmenovány po Palu Turanovi , který je použil k prokázání Turanova teorému , důležitého výsledku v extrémní teorii grafů .

Podle Dirichletova principu každá sada r + 1 vrcholů v Turanově grafu zahrnuje dva vrcholy ze stejného zlomku grafu. Turanův graf tedy neobsahuje kliku o velikosti r + 1. Podle Turanova teorému má Turanův graf maximální možný počet hran mezi všemi grafy bez klik o velikosti r + 1, které mají n vrcholů. Kivash a Sudakov (Keevash a Sudakov, 2003) ukázali, že Turanův graf je jediný graf bez kliky velikosti r + 1 řádu n , ve kterém má jakákoli podmnožina vrcholů α n alespoň hrany, pokud je α dostatečně blízko 1 . Erdős–Stoneova věta rozšiřuje Turanův teorém omezením počtu hran v grafu, který nemá pevný Turanův graf jako podgraf. V důsledku této věty lze v teorii extrémních grafů pro jakýkoli zakázaný podgraf dokázat podobné hranice v závislosti na chromatickém čísle podgrafu. ${\frac {r\,{-}\,1}{2r}}(2\alpha -1)n^{2}$

Zvláštní příležitosti

Některé hodnoty parametru r Turanových grafů vedou k pozoruhodným grafům, které jsou studovány samostatně.

Turanův graf T (2 n , n ) lze získat odstraněním dokonalé shody z úplného grafu K 2 n . Jak ukazuje Roberts ( Roberts 1969 ), rámec tohoto grafu je přesně n . Tento hrabě je někdy označován jako hrabě z Roberts . Tento graf je také 1- skeleton n - rozměrný cograph . Například graf T (6,3) = K 2,2,2 je grafem pravidelného osmistěnu . Pokud na večírek přijde n párů a každý si potřese rukou se všemi kromě svého partnera, pak tento graf popisuje sadu podání rukou. Z tohoto důvodu je také označován jako Cocktail Party Count .

Turanův graf T ( n ,2) je úplný bipartitní graf , a pokud je n sudé, jedná se o Mooreův graf . Jestliže r je dělitel n , je Turanův graf symetrický a silně regulární , ačkoli někteří autoři považují Turanovy grafy za triviální případ silné pravidelnosti, a proto je vylučují z definice silně regulárních grafů.

Turana graf má 3 a 2 b největší kliky , kde 3 a + 2 b = n a b ≤ 2. Každá největší klika je tvořena výběrem jednoho vrcholu z každého podílu. Tento počet největších klik je největší možný ze všech grafů s n vrcholy, bez ohledu na počet hran v grafu (Moon a Moser, 1965). Tyto grafy se někdy nazývají Moon-Moserovy grafy . $T(n,\lceil n/3\rceil )$

Další vlastnosti

Jakýkoli graf Turan je kograph . Lze jej tedy vytvořit z jednotlivých vrcholů posloupností operací disjunktního sjednocení a doplňku . Taková posloupnost může být zahájena zejména vytvořením všech nezávislých souborů Turanova grafu jako disjunktního spojení izolovaných vrcholů. Pak je celý graf doplňkem disjunktivního sjednocení doplňků těchto nezávislých množin.

Chao a Novacky (1982) ukázali, že Turanovy grafy jsou chromaticky jedinečné — žádné jiné grafy nemají stejné chromatické polynomy . Nikiforov (Nikiforov, 2005) použil Turanovy grafy k nalezení spodní hranice pro součet k -tých vlastních hodnot grafu a jeho doplňku.

Falls, Powell a Snoeyink vyvinuli účinný algoritmus pro nalezení shluků ortologních genových skupin v genomu reprezentováním dat jako graf a hledáním velkých turanských podgrafů.

Turanovy grafy mají také řadu zajímavých vlastností souvisejících s teorií geometrických grafů . Pór a Wood (2005) uvádějí dolní mez Ω(( rn ) 3/4 ) pro jakékoli vložení trojrozměrného Turanova grafu. Witsenhausen (1974) předpokládal, že maximálního součtu čtverců vzdáleností mezi n body uvnitř koule v R d jednotkového průměru je dosaženo na konfiguraci vytvořené vložením Turanova grafu do vrcholů pravidelného simplexu.

Graf G s n vrcholy je podgrafem Turanova grafu T ( n , r ) právě tehdy, když G připouští spravedlivé zabarvení v r barvách. Rozklad Turanova grafu na nezávislé množiny odpovídá rozkladu G do barevných tříd. Konkrétně Turanův graf je jediným n -vertexovým maximálním grafem se spravedlivým zabarvením v r barvách.

Poznámky

Literatura

C. Y. Chao, G. A. Novácký. Na maximálně nasycených grafech // Diskrétní matematika. - 1982. - T. 41 , no. 2 . — S. 139–143 . - doi : 10.1016/0012-365X(82)90200-X .
Craig Falls, Bradford Powell, Jack Snoeyink. Výpočet vysoce přísných COG pomocí grafů typu Turan.
Peter Keevash, Benny Sudakov. Místní hustota v grafech se zakázanými podgrafy // Kombinatorika, pravděpodobnost a výpočty. - 2003. - T. 12 , no. 2 . — S. 139–153 . - doi : 10.1017/S0963548302005539 .
JW Moon, L. Moser. O klikách v grafech // Israel Journal of Mathematics. - 1965. - T. 3 . — S. 23–28 . - doi : 10.1007/BF02760024 .
Vladimír Nikiforov. Problémy vlastních čísel typu Nordhaus-Gaddum . - 2005. - arXiv : math.CO/0506260 .
Attila Pór, David R Wood. Proč. Int. Symp. Grafická kresba (G.D. 2004) . — Poznámky k přednášce z informatiky č. 3383, Springer-Verlag, 2005, s. 395–402. - doi : 10.1007/b105810 .
FS Roberts. Nedávný pokrok v kombinatorice. - Academic Press, 1969. - S. 301-310.
P. Turan. K extrémnímu problému v teorii grafů // Matematiko Fizicki Lapok. - 1941. - T. 48 . — S. 436–452 .
HS Witsenhausen. Na maximu součtu čtverců vzdáleností pod omezením průměru // American Mathematical Monthly . — The American Mathematical Monthly, sv. 81, č.p. 10, 1974. - V. 81 , no. 10 . - S. 1100-1101 . - doi : 10.2307/2319046 . — .

Odkazy

Weisstein, Eric W. Cocktail Party Graph na Wolfram MathWorld .
Weisstein, Eric W. Octahedral Graph (anglicky) na webových stránkách Wolfram MathWorld .
Weisstein, Eric W. Turán Graph (anglicky) na webových stránkách Wolfram MathWorld .