Turanov graf

Turanov graf T(n,r) je kompletni multipartitni graf sačinjen deljenjem seta n temena na r podsetova, sa veličinama koje su što je više moguće jednake, i povezuju dva temena ivicom kad god pripadaju različitim podsetovima. Graf će imati (n mod r) podsetova veličine [n/r], i r - (n mod r) podsetova veličine [n/r]. To je kompletan r-partitan graf

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

Svako teme ima stepen ili n-[n/r] ili n-[n/r]. Broj ivica je:

${\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}}.$

To je regularan graf, ako je n deljivo s r.

Turanova teorema

Turanovi grafovi su dobili naziv po Pal Turanu, koji ih je koristio kako bi dokazao Turanovu teoremu, važan rezultat u ekstremalnoj teoriji grafova.

Po principu golublje rupe, svaki set od r+1 temena u Turanovom grafu uključuje dva temena na istoj particiji podseta; dakle, Turanov graf ne sadrži kliku veličine r+1. Prema Turanovoj teoremi, Turanov graf ima najveći mogući broj ivica od svih (r+1)-grafova bez klika sa n temena. Kevaš i Sudakov (2003) su pokazali da je Turanov graf takođe jedini (r+1)-graf bez klika reda n u kome svaki podset od αn temena pokriva najmanje  {\frac {r\,{-}\,1}{2r}}(2\alpha -1)n^{2} ivica, ako je α dovoljno blizu 1. 

Erdos-Stounova teorema nasleđuje Turanovu teoremu spajajući broj ivica u grafu koje nemaju fiksiran Turanov graf kao podgraf. Preko ove teoreme, slične veze u ekstremalnoj teoriji grafova mogu biti dokazane za bilo koji isključeni podgraf, u zavisnosti od hromatskog broja podgrafa.

Posebni slučajevi

The octahedron, a cross polytope whose edges and vertices form a Turán graph T(6,3).

Nekoliko izbora parametra r u Turanovom Grafu dovodi do notabilnih grafova koji se nezavisno proučavaju.

Turanov graf T(2n,n) može biti formiran uklanjanjem savršeno odgovarajućih od a kompletnog grafa K2n. Kako je Roberts (1969) pokazao, ovaj graf je takođe 1-skeleton od n-dimenzionalnog unakrs-politopa; na primer, graf T(6,3) = k2,2,2 je oktaedralni graf, graf regularnog oktaedra. ako n parova odu na žurku a, i svaka osoba se rukuje sa svakom osobom osim sa svojim partnerom, onda ovaj graf opisuje set rukovanja koja su se odigrala; iz ovog razloga takođe se naziva i koktel žurka graf.

Turanov graf T(n,2) je kompletan bipartitni graf i, kada je n jednako, Murov graf. Kada je r delilac od n, Turanov graf je simetričan i strogo regularan, iako neki autori smatraju Turanove grafove trivijalnim slučajevima stroge regularnosti i dalje ih isključuju iz definicije strogo regularnog grafa.

Turanov graf $T(n,\lceil n/3\rceil )$ ima 3^a2^b maksimalnih klikova, gde 3a + 2b = n i b ≤ 2; svaki maksimalni klik se formira biranjem jednog temena iz svake particije podseta. Ovo je najveći mogući broj maksimalnih klikova među svim n-temenim grafovima nezavisno od broja ivica u grafu (Mun i Mozer 1965); ovi grafovi se ponekad nazivaju Mun-Mozerovi grafovi.

Ostale osobine

Svaki Turanov graf je kograf; može biti formiran od individualnih temena od strane sekvenci disjunktnih unija i komplementnih operacija. Specifično, takva sekvenca može početi formiranjem svakog od nezavisnih setova Turanovog grafa kao disjunktna unija izolovanih temena. Tada, ukupni graf je komplement disjunktnih unija komplemenata ovih nezavisnih setova.

Čao i Novacki (1982) pokazuju da su Turanovi grafovi hromatično jedinstveni: nijedni drugi grafovi nemaju istie hromatske polinomijale. Nikiforov (2005) koristi Turanove grafove da snabde donju granicu sume  kte svojstvene vrednosti grafa i njegovog komplementa.

Fals, Pavel, i Snoejink su razvili efikasan algoritam za nalženje klastera ortolognih grupa gena u genomnim podacima, predstavljanjem podataka kao graf i i traženjem velikih Turanovih podgrafova.

Turanovi grafovi takođe imaju neke interesantne osobine povezane sa geometrijskom teorijom grafova. Por i Vud (2005) su pronašli nižu granicu od Ω((rn)^3/4) na zapremini bilo kog tri-dimenzionalnog, sa ugrađenom mrežom, Turanovog grafa. Vitsenhausen (1974) pretpostavlja da je maksimalna suma od kvadratnih distanci, među n tačaka sa jediničnim prečnikom u R^d, je postignut za konfiguracijom formiranom ugradnjom Turanovog grafa na temena regularnog simpleksa.

N-temeni graf G je podgraf Turanovog grafa T(n,r) ako i samo ako G priznaje pravedno bojenje sa r boja. Particija Turanovog grafa u nezavisnim setovima korespondira particiji G u klase boja. Naročito, Turanov graf je jedinstven masimalni n-temeni graf sa  r-boja pravedno obojenih.

Literatura

• Chao, C. Y.; Novacky, G. A. (1982). „On maximally saturated graphs”. Discrete Mathematics. 41 (2): 139—143. doi:10.1016/0012-365X(82)90200-X. 
• Falls, Craig; Powell, Bradford; Snoeyink, Jack. „Computing high-stringency COGs using Turán type graphs” (PDF). 
• Keevash, Peter; Sudakov, Benny (2003). „Local density in graphs with forbidden subgraphs”. Combinatorics, Probability and Computing. 12 (2): 139—153. doi:10.1017/S0963548302005539. 
• Moon, J. W.; Moser, L. (1965). „On cliques in graphs”. Israel Journal of Mathematics. 3: 23—28. doi:10.1007/BF02760024. 
• Nikiforov, Vladimir (2005). „Eigenvalue problems of Nordhaus-Gaddum type”. arXiv:math.CO/0506260 . 
• Pór, Attila; Wood, David R. (2005). „No-three-in-line-in-3D”. Proc. Int. Symp. Graph Drawing (GD 2004). Lecture Notes in Computer Science no. 3383, Springer-Verlag. str. 395—402. doi:10.1007/b105810. 
• Roberts, F. S. (1969). „Recent Progress in Combinatorics”. Academic Press: 301—310.  |contribution= ignored (help)
• Turán, P. (1941). „On an extremal problem in graph theory”. Matematiko Fizicki Lapok. 48: 436—452. 
• Witsenhausen, H. S. (1974). „On the maximum of the sum of squared distances under a diameter constraint”. American Mathematical Monthly. The American Mathematical Monthly, Vol. 81, No. 10. 81 (10): 1100—1101. JSTOR 2319046. doi:10.2307/2319046. 

Spoljašnje veze

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