53 175
редагувань
Граф Турана: відмінності між версіями
нема опису редагування
(Створено шляхом перекладу сторінки «Граф Турана») |
Немає опису редагування |
||
|
{{Граф
| 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=Граф Турана}}
[[Категорія
[[Категорія
| |||