Turánův graf - Turán graph - Wikipedia

Turánův graf
Turánův graf T (13,4)
Pojmenoval podle	Pál Turán
Vrcholy	n
Hrany	~${ displaystyle { frac {(r-1) n ^ {2}} {2r}}}$
Poloměr	${ displaystyle left {{ begin {pole} {ll} infty & r = 1 2 & r leq n / 2 1 & { text {jinak}} end {pole}} vpravo.}$
Průměr	${ displaystyle left {{ begin {pole} {ll} infty & r = 1 1 & r = n 2 & { text {jinak}} end {pole}} vpravo.}$
Obvod	${ displaystyle left {{ begin {pole} {ll} infty & r = 1 vee (n leq 3 wedge r leq 2) 4 & r = 2 3 & { text {jinak}} end {pole}} vpravo.}$
Chromatické číslo	r
Zápis	T(n,r)
Tabulka grafů a parametrů

The Turánův graf T(n,r) je kompletní multipartitní graf tvořil rozdělení sady z n vrcholy do r podmnožiny s co nejrovnější velikostí a spojením dvou vrcholů hranou právě tehdy, pokud patří do různých podmnožin. Graf bude mít ${ displaystyle (n , { bmod {,}} r)}$ podmnožiny velikosti ${ displaystyle lceil n / r rceil}$, a ${ displaystyle r- (n , { bmod {,}} r)}$ podmnožiny velikosti ${ displaystyle lfloor n / r rfloor}$. To znamená, že je kompletní r-částový graf

${ Displaystyle K _ { lceil n / r rceil, lceil n / r rceil, ldots, lfloor n / r rfloor, lfloor n / r rfloor}.}$

Každý vrchol má buď stupeň ${ Displaystyle n- lceil n / r rceil}$ nebo ${ displaystyle n- lpodlaha n / r rpodlaha}$. Počet hran je

${ displaystyle { frac {n (n-1)} {2}} - (n , { bmod {,}} r) { frac { lceil n / r rceil ( lceil n / r rceil -1)} {2}} - (r- (n , { bmod {,}} r)) { frac { lfloor n / r rfloor ( lfloor n / r rfloor -1 )} {2}} leq left (1 - { frac {1} {r}} right) { frac {n ^ {2}} {2}}.}$

Je to běžný graf -li n je dělitelné r.

Turánova věta

Turánské grafy jsou pojmenovány po Pál Turán, který je použil k prokázání Turánova věta, důležitý výsledek v teorie extrémních grafů.

Podle principu pigeonhole každá sada r + 1 vrcholy v grafu Turán zahrnují dva vrcholy ve stejné podmnožině oddílů; proto Turánův graf neobsahuje a klika velikostir + 1. Podle Turánovy věty má Turánův graf maximální možný počet hran ze všech (r + 1) bezklikové grafy s n vrcholy. Keevash a Sudakov (2003) ukazují, že Turánův graf je také jediný (r + 1) bezklikový graf objednávky n ve kterém každá podmnožina αn vrcholy pokrývají minimálně ${ displaystyle { frac {r , {-} , 1} {3r}} (2 alpha -1) n ^ {2}}$ hrany, pokud je α dostatečně blízko k 1. The Erdős – kamenná věta rozšiřuje Turánovu větu ohraničením počtu hran v grafu, který nemá pevný Turánův graf jako podgraf. Pomocí této věty lze podobné meze v teorii extrémních grafů dokázat pro jakýkoli vyloučený podgraf, v závislosti na chromatické číslo podgrafu.

Speciální případy

The osmistěn, 3-křížový mnohostěn jehož hrany a vrcholy se tvoří K._2,2,2, Turánův graf T(6,3). Nepřipojené vrcholy dostávají stejnou barvu v této projekci zaměřené na tvář.

Několik možností parametru r v Turánově grafu vedou k významným grafům, které byly nezávisle studovány.

Turánův graf T(2n,n) lze vytvořit odstraněním a perfektní shoda od a kompletní graf K._2n. Tak jako Roberts (1969) tento graf ukázal boxicita přesně n; to je někdy známé jako Robertsův graf. Tento graf je takékostra z n-dimenzionální křížový mnohostěn; například graf T(6,3) = K._2,2,2 je oktaedrický graf, graf regulárního osmistěn. Li n páry jdou na večírek a každý si potřásá rukou s každým, s výjimkou svého partnera, pak tento graf popisuje sadu potřesení rukou, která se koná; z tohoto důvodu se také nazývá koktejlový večírek graf.

Turánův graf T(n, 2) je a kompletní bipartitní graf a kdy n je sudý, a Mooreův graf. Když r je dělitel n, Turánův graf je symetrický a velmi pravidelné, ačkoli někteří autoři považují Turánovy grafy za triviální případ silné pravidelnosti, a proto je vylučují z definice silně pravidelného grafu.

Turánův graf ${ displaystyle T (n, lceil n / 3 rceil)}$ má 3^A2^b maximální kliky, kde3A + 2b = n a b ≤ 2; každá maximální klika je vytvořena výběrem jednoho vrcholu z každé podmnožiny oddílu. Toto je největší počet maximálních možných klik ze všech n-vertexové grafy bez ohledu na počet hran v grafu (Moon a Moser 1965); tyto grafy se někdy nazývají Grafy Měsíc – Moser.

Další vlastnosti

Každý Turánův graf je a cograph; to znamená, že jej lze vytvořit z jednotlivých vrcholů posloupností disjunktní unie a doplněk operace. Konkrétně taková posloupnost může začít vytvořením každé z nezávislých sad Turánova grafu jako disjunktního spojení izolovaných vrcholů. Pak je celkový graf doplňkem disjunktního sjednocení doplňků těchto nezávislých množin.

Chao a Novacky (1982) ukazují, že Turánovy grafy jsou chromaticky jedinečný: žádné jiné grafy nemají stejné chromatické polynomy. Nikiforov (2005) používá Turánovy grafy k poskytnutí dolní hranice pro součet kth vlastní čísla grafu a jeho doplnění.

Falls, Powell a Snoeyink vyvíjejí efektivní algoritmus pro hledání shluků ortologních skupin genů v datech genomu, reprezentováním dat jako grafu a hledáním velkých Turánových podgrafů.

Turánovy grafy mají také některé zajímavé vlastnosti teorie geometrických grafů. Pór a Wood (2005) dávají spodní hranici Ω ((rn)^3/4) na objem libovolného trojrozměrného vkládání mřížky Turánova grafu. Witsenhausen (1974) předpokládá, že maximální součet čtverců vzdáleností mezi n body s průměrem jednotky v R^d, je dosaženo pro konfiguraci vytvořenou vložením grafu Turán na vrcholy pravidelného simplexu.

An n-vrcholový graf G je podgraf turánského grafu T(n,r) právě tehdy G připouští spravedlivé zbarvení s r barvy. Rozdělení Turánova grafu na nezávislé množiny odpovídá rozdělení G do barevných tříd. Zejména Turánův graf je jedinečným maximem n-vrcholový graf s r-barevné spravedlivé zbarvení.

Reference

• Chao, C. Y .; Novacky, G. A. (1982). "Na maximálně nasycených grafech". Diskrétní matematika. 41 (2): 139–143. doi:10.1016 / 0012-365X (82) 90200-X.CS1 maint: ref = harv (odkaz)
• Falls, Craig; Powell, Bradford; Snoeyink, Jacku. "Výpočet vysoce přísných COG pomocí grafů typu Turán" (PDF). Citovat deník vyžaduje | deník = (Pomoc)CS1 maint: ref = harv (odkaz)
• Keevash, Peter; Sudakov, Benny (2003). "Místní hustota v grafech se zakázanými podgrafy" (PDF). Kombinatorika, pravděpodobnost a výpočet. 12 (2): 139–153. doi:10.1017 / S0963548302005539.CS1 maint: ref = harv (odkaz)
• Moon, J. W .; Moser, L. (1965). "Na kliky v grafech". Israel Journal of Mathematics. 3: 23–28. doi:10.1007 / BF02760024.CS1 maint: ref = harv (odkaz)
• Nikiforov, Vladimir (2005). "Problémy s vlastním číslem typu Nordhaus-Gaddum". arXiv:math.CO/0506260.CS1 maint: ref = harv (odkaz)
• Pór, Attila; Wood, David R. (2005). „No-three-in-line-in-3D“. Proc. Int. Symp. Kreslení grafu (GD 2004). Přednášky z informatiky č. 3383, Springer-Verlag. 395–402. doi:10.1007 / b105810. hdl:11693/27422.
• Roberts, F. S. (1969). Tutte, W.T. (ed.). "O boxicitě a kubicitě grafu". Nedávný pokrok v kombinatorice: 301–310.CS1 maint: ref = harv (odkaz)
• Turán, P. (1941). „Egy gráfelméleti szélsőértékfeladatról (K extrémnímu problému v teorii grafů)“. Matematikai a Fizikai Lapok. 48: 436–452.CS1 maint: ref = harv (odkaz)
• Witsenhausen, H. S. (1974). "Na maximum součtu čtverců vzdáleností pod omezením průměru". Americký matematický měsíčník. 81 (10): 1100–1101. doi:10.2307/2319046. JSTOR  2319046.CS1 maint: ref = harv (odkaz)

externí odkazy

• Weisstein, Eric W. „Cocktail Party Graph“. MathWorld.
• Weisstein, Eric W. "Octahedral Graph". MathWorld.
• Weisstein, Eric W. "Turán Graph". MathWorld.