Граф Турана: відмінності між версіями

Перейти до навігації Перейти до пошуку
нема опису редагування
(Створено шляхом перекладу сторінки «Граф Турана»)
 
Немає опису редагування
{{Граф}}
| name = Граф Турана
| image = [[Image:Turan 13-4.svg|180px]]
| image_caption = Граф Турана T(13,4)
| namesake = [[Пал Туран]]
| vertices = ''n''
| edges = ~<math>\frac{(r - 1) n^2}{2 r}</math>
| radius = <math>\left\{\begin{array}{ll}\infty & r = 1\\ 2 & r \le n/2\\ 1 & \text{otherwise}\end{array}\right.</math>
| diameter = <math>\left\{\begin{array}{ll}\infty & r = 1\\ 1 & r = n\\ 2 & \text{otherwise}\end{array}\right.</math>
| girth = <math>\left\{\begin{array}{ll}\infty & r = 1 \vee (n \le 3 \wedge r \le 2)\\ 4 & r = 2\\ 3 & \text{otherwise}\end{array}\right.</math>
| chromatic_number = ''r''
| chromatic_index =
| notation = ''T''(''n'',''r'')
}}
 
'''Граф Турана''' ''T''(''n'',''r'') — це граф, утворений розкладанням ''n'' вершин на ''r'' підмножин, з якомога ближчим розміром, і вершини в цьому графі з'єднані ребром, якщо вони належать різним підмножинам. Граф буде мати <math>(n\,\bmod\,r)</math> підмножин розміром <math>\lceil n/r\rceil</math> і <math>r-(n\,\bmod\,r)</math> підмножин розміром <math>\lfloor n/r\rfloor</math>. Таким чином, це [[Багаточастковий граф|повний ''r''-частковий граф]]
 
Граф ''G'' з ''n'' вершинами є підграфом графа Турана ''T''(''n'',''r'') [[тоді й лише тоді]], коли ''G'' допускає [[рівномірне розфарбування]] в ''r'' кольорів. Розкладання графа Турана на незалежні множини відповідає розкладанню ''G'' на класи кольорів. Зокрема, граф Турана є єдиним максимальним графом з ''n'' вершинами з рівномірним розфарбуванням у ''r'' кольорів.
 
== Примітки ==
 
== Література ==
 
* {{Стаття|author=C. Y. Chao, G. A. Novacky|title=On maximally saturated graphs|видання=Discrete Mathematics|том=41|pages=139–143|date=1982|doi=10.1016/0012-365X(82)90200-X|ref=Chao, Novacky|issue=2}}
* {{Стаття|title=Computing high-stringency COGs using Turán type graphs|author=Craig Falls, Bradford Powell, Jack Snoeyink|url=http://www.cs.unc.edu/~snoeyink/comp145/cogs.pdf|ref=Falls, Powell, Snoeyink}}
 
== Посилання ==
 
* {{Mathworld||urlname=CocktailPartyGraph|title=Cocktail Party Graph}}
* {{Mathworld||urlname=OctahedralGraph|title=Граф октаедра}}
* {{Mathworld||urlname=TuranGraph|title=Граф Турана}}
 
[[Категорія:Category:Види графів]]
[[Категорія:Category:Екстремальна теорія графів]]

Навігаційне меню