Туранов граф

Туранов граф T(н,р) је комплетни мултипартитни граф сачињен дељењем сета н темена на р подсетова, са величинама које су што је више могуће једнаке, и повезују два темена ивицом кад год припадају различитим подсетовима. Граф ће имати (н мод р) подсетова величине [н/р], и р - (н мод р) подсетова величине [н/р]. То је комплетан р-партитан граф

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

То је регуларан граф, ако је н дељиво с р.

Туранова теорема

Туранови графови су добили назив по Пал Турану, који их је користио како би доказао Туранову теорему, важан резултат у екстремалној теорији графова.

По принципу голубље рупе, сваки сет од р+1 темена у Турановом графу укључује два темена на истој партицији подсета; дакле, Туранов граф не садржи клику величине р+1. Према Турановој теореми, Туранов граф има највећи могући број ивица од свих (р+1)-графова без клика са н темена. Кеваш и Судаков (2003) су показали да је Туранов граф такође једини (р+1)-граф без клика реда н у коме сваки подсет од αн темена покрива најмање  {\frac {r\,{-}\,1}{2r}}(2\alpha -1)n^{2} ивица, ако је α довољно близу 1. 

Ердос-Стоунова теорема наслеђује Туранову теорему спајајући број ивица у графу које немају фиксиран Туранов граф као подграф. Преко ове теореме, сличне везе у екстремалној теорији графова могу бити доказане за било који искључени подграф, у зависности од хроматског броја подграфа.

Посебни случајеви

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

Неколико избора параметра р у Турановом Графу доводи до нотабилних графова који се независно проучавају.

Туранов граф T(2н,н) може бити формиран уклањањем савршено одговарајућих од а комплетног графа K2n. Како је Робертс (1969) показао, овај граф је такође 1-скелетон од н-димензионалног унакрс-политопа; на пример, граф Т(6,3) = к2,2,2 је октаедрални граф, граф регуларног октаедра. ако н парова оду на журку а, и свака особа се рукује са сваком особом осим са својим партнером, онда овај граф описује сет руковања која су се одиграла; из овог разлога такође се назива и коктел журка граф.

Туранов граф Т(н,2) је комплетан бипартитни граф и, када је н једнако, Муров граф. Када је р делилац од н, Туранов граф је симетричан и строго регуларан, иако неки аутори сматрају Туранове графове тривијалним случајевима строге регуларности и даље их искључују из дефиниције строго регуларног графа.

Туранов граф $T(n,\lceil n/3\rceil )$ има 3^a2^b максималних кликова, где 3a + 2b = n и b ≤ 2; сваки максимални клик се формира бирањем једног темена из сваке партиције подсета. Ово је највећи могући број максималних кликова међу свим n-теменим графовима независно од броја ивица у графу (Мун и Мозер 1965); ови графови се понекад називају Мун-Мозерови графови.

Остале особине

Сваки Туранов граф је кограф; може бити формиран од индивидуалних темена од стране секвенци дисјунктних унија и комплементних операција. Специфично, таква секвенца може почети формирањем сваког од независних сетова Турановог графа као дисјунктна унија изолованих темена. Тада, укупни граф је комплемент дисјунктних унија комплемената ових независних сетова.

Чао и Новацки (1982) показују да су Туранови графови хроматично јединствени: ниједни други графови немају истие хроматске полиномијале. Никифоров (2005) користи Туранове графове да снабде доњу границу суме  kте својствене вредности графа и његовог комплемента.

Фалс, Павел, и Сноејинк су развили ефикасан алгоритам за налжење кластера ортологних група гена у геномним подацима, представљањем података као граф и и тражењем великих Туранових подграфова.

Туранови графови такође имају неке интересантне особине повезане са геометријском теоријом графова. Пор и Вуд (2005) су пронашли нижу границу од Ω((rn)^3/4) на запремини било ког три-димензионалног, са уграђеном мрежом, Турановог графа. Витсенхаусен (1974) претпоставља да је максимална сума од квадратних дистанци, међу n тачака са јединичним пречником у R^d, је постигнут за конфигурацијом формираном уградњом Турановог графа на темена регуларног симплекса.

Н-темени граф G је подграф Турановог графа T(n,r) ако и само ако G признаје праведно бојење са r боја. Партиција Турановог графа у независним сетовима кореспондира партицији G у класе боја. Нарочито, Туранов граф је јединствен масимални n-темени граф са  r-боја праведно обојених.

Литература

• 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. стр. 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. 

Спољашње везе

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