Turana grófja

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. október 9-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Turana grófja

Valaki után elnevezve	Turán Pál
Csúcsok	n
borda	$\left\lfloor {\frac {(r-1)n^{2}}{2r}}\right\rfloor$
Sugár	$\left\{{\begin{array}{ll}\infty &r=1\\2&r\leq n/2\\1&{\text{otherwise}}\end{array}}\right.$
Átmérő	$\left\{{\begin{array}{ll}\infty &r=1\\1&r=n\\2&{\text{otherwise}}\end{array}}\right.$
Heveder	$\left\{{\begin{array}{ll}\infty &r=1\vee (n\leq 3\wedge r\leq 2)\\4&r=2\\3&{\text{egyébként)) \end{tömb}}\jobbra.$
Kromatikus szám	r
Kijelölés	= T ( n , r )
Médiafájlok a Wikimedia Commons oldalon

A T ( n , r ) Turan gráf egy n csúcs r részhalmazra bontásával kialakított gráf , amelynek mérete a lehető legközelebb van, és ebben a gráfban a csúcsokat egy él köti össze, ha különböző részhalmazokhoz tartoznak. A grafikon méretű részhalmazokat és méret részhalmazokat tartalmaz . Tehát ez egy teljes r -részes gráf $(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 }.

Minden csúcsnak van foka vagy , vagy . Az élek száma az $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))\lfloor n/r\rfloor ^{2})\leq \left(1-{\frac {1}{r}}\right){\frac { n^{2}}{2}}.

Egy gráf szabályos , ha n osztható r -rel .

Turan-tétel

A Turan gráfokat Turan Pálról nevezték el , aki Turan tételének bizonyítására használta őket , ami az extrém gráfelmélet egyik fontos eredménye .

A Dirichlet-elv szerint egy Turan-gráfban minden r + 1 csúcshalmaz két csúcsot tartalmaz a gráf ugyanabból a törtrészéből. Így a Turan-gráf nem tartalmaz r + 1 méretű klikket . A Turan-tétel szerint a Turan-gráfnak a lehető legtöbb éle van az összes r + 1 méretű, n csúcsú klikket nem tartalmazó gráf közül. Kivash és Sudakov (Keevash és Sudakov, 2003) kimutatta, hogy a Turan-gráf az egyetlen gráf, ahol nincsenek r + 1 méretű n -rendű klikkek, amelyekben az α n csúcsok bármely részhalmazának vannak legalább élei, ha α kellően közel van 1-hez . Az Erdős–Stone-tétel kiterjeszti a Turan-tételt az élek számának korlátozásával egy olyan gráfban, amelynek részgráfja nem tartalmaz rögzített Turan-gráfot. Ebből a tételből következően az extremális gráfok elméletében bármely tiltott részgráfra hasonló korlátokat lehet bizonyítani a részgráf kromatikus számától függően . ${\frac {r\,{-}\,1}{2r}}(2\alpha -1)n^{2}$

Különleges alkalmak

A Turan-gráfok r paraméterének egyes értékei figyelemre méltó grafikonokhoz vezetnek, amelyeket külön tanulmányozunk.

A T (2 n , n ) Turan-gráfot úgy kaphatjuk meg, hogy a K 2 n teljes gráfból eltávolítunk egy tökéletes illeszkedést . Amint azt Roberts ( Roberts 1969 ) mutatja, ennek a gráfnak a kerete pontosan n . Ezt a grófot néha Roberts grófjának is nevezik . Ez a gráf egy 1- vázas n - dimenziós kográf is . Például a T (6,3) = K 2,2,2 gráf egy szabályos oktaéder gráfja . Ha n pár jön egy buliba, és mindenki kezet fog mindenkivel, kivéve a partnerét, akkor ez a grafikon a kézfogások sorozatát írja le. Emiatt a koktélparti grófjaként is emlegetik .

A T ( n ,2) Turan-gráf egy teljes kétrészes gráf , és ha n páros, akkor Moore-gráf . Ha r osztója n -nek, akkor a Turan-gráf szimmetrikus és erősen reguláris , bár egyes szerzők a Turan-gráfokat erős szabályszerűség triviális esetének tartják, ezért kizárják őket az erősen szabályos gráfok definíciójából.

A Turana-gráfnak 3 a 2 b legnagyobb klikkje van , ahol 3 a + 2 b = n és b ≤ 2. Minden legnagyobb klikket úgy alakítunk ki, hogy minden megosztásból kiválasztunk egy csúcsot. A legnagyobb klikkek száma a lehető legnagyobb az összes n csúcsú gráf között, függetlenül a gráf éleinek számától (Moon és Moser, 1965). Ezeket a grafikonokat néha Hold-Moser grafikonoknak is nevezik . $T(n,\lceil n/3\rceil )$

Egyéb tulajdonságok

Bármely Turan-gráf egy kográf . Így létrehozható az egyes csúcsokból a diszjunkt unió és komplement műveletsorával . Egy ilyen sorozatot különösen úgy lehet elindítani, hogy a Turan-gráf összes független halmazát izolált csúcsok diszjunkt uniójaként képezzük. Ekkor az egész gráf e független halmazok komplementerei diszjunktív uniójának komplementere.

Chao és Novacky (1982) kimutatta, hogy a Turan-gráfok kromatikusan egyediek – egyetlen másik gráfnak sincs azonos kromatikus polinomja . Nikiforov (Nikiforov, 2005) Turan-gráfokat használt, hogy megtalálja a gráf k - edik sajátértékének és komplementerének összegének alsó korlátját.

Falls, Powell és Snoeyink hatékony algoritmust fejlesztettek ki az ortológ géncsoportok klasztereinek megtalálására a genomban az adatok grafikonként való ábrázolásával és nagy Turan-részgráfok keresésével.

A turáni gráfoknak számos érdekes tulajdonsága is van a geometriai gráfelmélettel kapcsolatban . Pór és Wood (2005) alsó korlátot ad Ω(( rn ) 3/4 ) bármely háromdimenziós Turan-gráf beágyazásra. Witsenhausen (1974) úgy sejtette, hogy az egységnyi átmérőjű R d golyó belsejében lévő n pont közötti távolságok maximális összegét a Turan-gráf szabályos szimplex csúcsaiba való beágyazásával képzett konfiguráción érjük el.

Egy n csúcsú G gráf a T ( n , r ) Turan gráf részgráfja akkor és csak akkor, ha G megengedi az r színben való tisztességes színezést . A Turan-gráf független halmazokra bontása megfelel G színosztályokra való bontásának. Konkrétan a Turan-gráf az egyetlen n csúcsú maximális gráf, amely r színben tisztességes színezéssel rendelkezik .

Jegyzetek

Irodalom

C. Y. Chao, G. A. Novacky. Maximálisan telített gráfokon // Discrete Mathematics. - 1982. - T. 41 , sz. 2 . – S. 139–143 . - doi : 10.1016/0012-365X(82)90200-X .
Craig Falls, Bradford Powell, Jack Snoeyink. Nagy szigorúságú COG-k számítása Turán típusú gráfok segítségével.
Peter Keevash, Benny Sudakov. Helyi sűrűség gráfokban tiltott részgráfokkal // Kombinatorika, valószínűség és számítás. - 2003. - T. 12 , sz. 2 . – S. 139–153 . - doi : 10.1017/S0963548302005539 .
JW Moon, L. Moser. A klikkekről grafikonokon // Israel Journal of Mathematics. - 1965. - T. 3 . – S. 23–28 . - doi : 10.1007/BF02760024 .
Vlagyimir Nyikiforov. Nordhaus-Gaddum típusú sajátérték-problémák . - 2005. - arXiv : math.CO/0506260 .
Pór Attila, David R Wood. Proc. Int. Symp. Graph Drawing (G.D. 2004) . — Számítástechnikai előadásjegyzetek sz. 3383, Springer-Verlag, 2005, 395–402. - doi : 10.1007/b105810 .
FS Roberts. A kombinatorika legújabb eredményei. - Akadémiai Kiadó, 1969. - S. 301-310.
P. Turan. Egy extrém problémáról a gráfelméletben // Matematiko Fizicki Lapok. - 1941. - T. 48 . – S. 436–452 .
HS Witsenhausen. Az átmérőkényszer alatti távolságok négyzetösszegének maximumáról // American Mathematical Monthly . – The American Mathematical Monthly, 4. évf. 81. sz. 10, 1974. - V. 81 , 1. sz. 10 . - S. 1100-1101 . - doi : 10.2307/2319046 . — .

Linkek

Weisstein, Eric W. Cocktail Party Graph a Wolfram MathWorldnél .
Weisstein, Eric W. Octahedral Graph (angol) a Wolfram MathWorld webhelyén .
Weisstein, Eric W. Turán Graph (angol) a Wolfram MathWorld weboldalán .