Перегляд вихідного коду сторінки Рівномірне розфарбування

{{вичитати}}
'''Рівномірне розфарбування''' в [[Теорія графів|теорії графів]]&nbsp;— це приписування [[Розфарбовування графів|кольорів]] [[Вершина (теорія графів)|вершинам]] [[Граф (математика)#Орієнтований граф|неорієнтованого графа]], таким чином, що:
* Ніякі дві суміжні вершини не мають однаковий колір,
* Число вершин у будь-яких двох колірних класах відрізняються більш ніж на одиницю.
Тобто, це процес розбиття вершин на різні кольори якомога більш рівномірним чином. Наприклад, для рівномірності слід давати кожній вершині свій власний колір, що призводить до того, що зазвичай, використовують набагато більше кольорів, ніж необхідно для оптимального розфарбування. Еквівалентний спосіб визначення рівномірного розфарбування є вкладенням даного графа як підграфа [[Граф Турана|графа Турана]]. Є два види [[Хроматичне число|хроматичних чисел]], які пов'язані з рівномірним розфарбуванням.<ref name="F06">{{harvtxt|Furmańczyk|2006}}.</ref> '''Рівномірним хроматичним числом '''графа ''G'' називається найменше число ''k'', при якому&nbsp;''G ''має рівномірне розфарбування з ''k'' кольорів. Але ''G'' може не мати рівномірного розфарбування для деякого великого числа кольорів; '''рівномірний хроматичний поріг''' ''G'' є найменше число ''k, ''при якому ''G'' має рівномірне розфарбування для будь-якої кількості кольорів більшої або рівної ''k''.<ref>Зауважимо, що коли ''k'' більше, ніж число вершин у графі, то тоді для рівномірного розфарбування з ''k'' кольорами кожен клас кольору містить нуль або одну вершину, отже, кожен граф має межу для рівномірного розфарбування.</ref>

'''Теорема Хайнала-Семереді''', подається як гіпотеза [[Пал Ердеш|Ердеша]] (1964) і доведена {{Нп|Андрас Хайнал|Хайналом||András Hajnal}} і [[Ендре Семереді|Семереді]] (1970). Вона стверджує, що будь-який граф з максимальним степенем Δ має рівномірне розфарбування з Δ + 1 кольорів. Для знаходження розфарбування застосовуються алгоритми [[Поліноміальна теорема|поліноміального часу]], ці алгоритми використовуються також для знаходження оптимального розфарбування спеціальних класів графів,<ref>{{Cite journal|title = A fast algorithm for equitable coloring|url = http://link.springer.com/article/10.1007/s00493-010-2483-5|journal = Combinatorica|date = 2010-09-17|issn = 0209-9683|pages = 217–224|volume = 30|issue = 2|doi = 10.1007/s00493-010-2483-5|first = Henry A.|last = Kierstead|first2 = Alexandr V.|last2 = Kostochka|first3 = Marcelo|last3 = Mydlarz|first4 = Endre|last4 = Szemerédi}}</ref> але є більш загальна проблема&nbsp;— чи має довільний граф [[NP-повна задача|NP-повне]] рівномірне розфарбування із заданою кількістю кольорів.

== Приклади ==
[[Файл:Equitable-K15.svg|thumb|Рівномірне розфарбування для зірки ''K''<sub>1,5</sub>.]]
Граф-зірка '''K<sub>1,5</sub>''', що показана на малюнку, є [[Повний двочастковий граф|повним двочастковим графом]], і, отже, може бути пофарбована у два кольори. Проте, у результаті такого розфарбування цей граф має одну вершину в одному кольоровому класі та п'ять в іншому, і тому таке розфарбування є нерівномірним. Найменше число кольорів в рівномірному розфарбуванні цього графа дорівнює чотирьом, як показано на малюнку: центральна вершина повинна бути єдиною вершиною в її колірному класі, так що інші п'ять вершин повинні бути розділені щонайменше на три колірних класи, аби гарантувати, що інші колірні класи мають не більше двох вершин. Таким чином, хроматичне число графа може відрізнятися від його рівномірного розфарбування на ''n/4''. Оскільки K<sub>1,5</sub> має максимальний степінь п'ять, кількість кольорів гарантованих для нього по теоремі Хайнала-Семереді&nbsp;— шість, досягається шляхом надання кожній вершині свого кольору.

== Теорема Хайнала&nbsp;— Семереді ==
[[Теорема Брукса]] свідчить, що будь-який зв'язний граф з максимальним степенем Δ має Δ-розфарбування, з двома винятками ([[Повний граф|повні графи]] і непарні цикли). Проте, це розфарбування може бути в цілому далеке від рівномірного. [[Ердеш Пал|Ердеш]] (1964) зробив припущення, що рівномірне розфарбування можливе тільки з більш ніж одним кольором: будь-який граф з максимальним Δ-степенем має рівномірне розфарбування з Δ + 1 кольорів. Випадок Δ = 2 є простим (будь-яке об'єднання шляхів і циклів можна правильно розфарбувати з використанням повторного малюнка з трьох кольорів, з незначними змінами до повторення при закритті циклу) і випадок Δ + 1 = ''n/3'' був вирішений раніше методом [[Корраді та Хайнала|Корраді та Хайнала (1963)]]. Повну гіпотезу довели Хайналом та Семереді (1970), і нині вона відома як '''теорема Хайнала&nbsp;— Семереді'''. Поліноміальний алгоритм часу для знаходження рівномірного розфарбування з великою кількістю кольорів був описаний у методі Кієрстада-Косточки. Кієрстад та Косточка також сформулювали, але не довели, посилення теореми, яка показує, що рівномірне ''k''-розфарбування існує щоразу, коли кожні дві суміжні вершини мають такі степені, що їх сума більше ніж 2''k'' + 1.

Мейер висловив припущення з [[Теорема Брукса|теореми Брукса]] для рівномірного розфарбування: кожен зв'язний граф з максимальним Δ-степенем має рівномірне розфарбування з Δ чи меншою кількістю кольорів, за винятком повних графів і непарних циклів. Посилений варіант гіпотези стверджує, що кожен такий граф має рівномірне розфарбування з точно Δ кольорів, з одним додатковим винятком, [[повний двочастковий граф]], в якому обидві двочасткові сторони мають однакове непарне число вершин.<ref name="F06"/>

Сеймур (1974) запропонував посилення теореми Хайнала&nbsp;— Семереді, до якого можна також віднести [[теорема Дірака|теорему Дірака]], що ''щільні графи''&nbsp;— [[Гамільтонів граф|Гамільтонові]]: він висловив припущення, що, якщо кожна вершина в ''n''-вершинному графі має хоча б ''kn/''(''k'' + 1) сусідів, тоді граф містить в ролі підграфа граф, утворений шляхом з'єднання вершин, які знаходяться у ''k'' кроках одна від одної в ''n''-циклі. Випадок ''k'' = 1 є теоремою Дірака. Теорема Хайнала&nbsp;— Семереді може бути взята з цієї гіпотези шляхом застосування гіпотези для великих значень ''k'' до [[доповнення графа]], даного графа, і з використанням як кольорів класів суміжних підпослідовностей вершин з ''n''-циклу. Гіпотеза Сеймура була доведена для графа, в якому ''n'' досить велике щодо ''k''; доведення використовує кілька складних фактів, включаючи саму теорему Хайнала&nbsp;— Семереді.

== Спеціальні класи графів ==
Для будь-якого дерева з максимальним степенем Δ, рівномірне хроматичне число щонайбільше
: <math>1+\lceil\Delta/2\rceil</math>

Проте, більшість дерев мають значно менші рівномірні хроматичні числа: якщо дерево з n вершинами має Δ ≤ n/3 − O(1), то воно має рівномірне розфарбування тільки з трьома кольорами. Фурманчук (2006) вивчає рівномірне хроматичне число добутку графів.

== Проблематика рівномірного розфарбовування ==
Також була розглянута проблема знаходження рівномірного розфарбування з найменшою кількістю кольорів. Перехід від розфарбування графа до рівномірного розфарбування можна довести додаванням достатньої кількості ізольованих вершин графа, таким чином, щоб граф був [[NP-повна задача|NP-повним]], це потрібно для перевірки того, що граф має рівномірне розфарбування з заданою кількістю кольорів (більш як два). Проте, ця проблема стає все більш цікавою, коли обмежується спеціальними класами графів або параметризацією. Бодлендер та Фомін (2005) показали, що якщо нам дано граф ''G'' і число с кольорів, тоді можна перевірити, чи допускає ''G'' справедливе ''с''-розфарбування в часі O(''n''<sup>O(''t'')</sup>), де ''t'' [[Деревна ширина (теорія графів)|деревна ширина]] ''G''; зокрема, рівномірне розфарбування можна отримати оптимальним чином за поліноміальний час для дерев (раніше відомі по Чен та Лі 1994) і [[зовніпланарний граф|зовніпланарних графів.]] Алгоритм поліноміального часу також використовується для рівномірного розфарбовування [[Розщеплюваний граф|розщеплюваних графів]].

== Додатки ==
Одним з прикладів застосування рівномірного розфарбування, запропонованим Меєром (1973), є розв'язок задачі про планування завдань. У цій задачі вершини графа являють собою набір завдань, які повинні бути виконані, і ребро з'єднує два завдання, які не повинні виконуватися одночасно. Розфарбування цього графа являє собою розбиття задач на підмножини, які можуть виконуватися одночасно; Таким чином, кількість кольорів у розфарбуванні відповідає кількості часових кроків, необхідних для виконання всього завдання. З міркувань [[балансування навантаження]], бажано виконувати рівні або майже рівні кількості завдань на кожному кроці, і це балансування саме те, що дозволяє досягти рівномірного розфарбування. Фурманчук (2006) згадує конкретне застосування такого роду проблеми планування, призначенням університетських курсів на тимчасових інтервалах таким чином, що розподіляє курси рівномірно серед доступних тимчасових інтервалів і дозволяє уникнути планування несумісних пари курсів одночасно.

Теорема Хайнала-Семереді також була використана для пов'язання [[Дисперсія випадкової величини|дисперсії]] сум випадкових величин з обмеженою залежністю. Якщо кожна змінна залежить від більшості Δ інших, тоді рівномірне розфарбування залежного графа може бути використане для поділу змінних на незалежні підмножини в межах яких може бути застосована [[нерівність Чернова]].

== Див. також ==
* [[Повне розфарбування]]
* [[Тотальне розфарбування]]

== Примітки ==
{{Reflist|2}}

== Примітки ==
{{refbegin|colwidth=30em}}
* {{citation
 | last1 = Bodlaender | first1 = Hans L. | author1-link = Hans L. Bodlaender
 | last2 = Fomin | first2 = Fedor V.
 | doi = 10.1016/j.tcs.2005.09.027
 | mr = 2183465
 | issue = 1
 | journal = Theoretical Computer Science
 | pages = 22–30
 | title = Equitable colorings of bounded treewidth graphs
 | volume = 349
 | year = 2005}}.
* {{citation | last1 = Bollobás | first1 = B. | last2= Eldridge | first2= S. E. | author1-link = Béla Bollobás | journal = [[Journal of Combinatorial Theory]] | series = Series B | pages = 105–124 | title = Packings of graphs and applications to computational complexity | volume = 25 | year = 1978 | doi = 10.1016/0097-3165(78)90073-0 | mr = 0511983}}.
* {{citation
 | last1 = Bollobás | first1 = Béla | author1-link = Béla Bollobás
 | last2 = Guy | first2 = Richard K. | author2-link = Richard K. Guy
 | doi = 10.1016/0095-8956(83)90017-5
 | mr = 703602
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]] | series = Series B
 | pages = 177–186
 | title = Equitable and proportional coloring of trees
 | volume = 34
 | year = 1983}}.
* {{citation | last = Catlin | first =  Paul A. | journal = Discrete Math. | pages = 225–233 | title = Subgraphs of graphs. I. | volume = 10 | year = 1974 | doi = 10.1016/0012-365X(74)90119-8 | mr = 0357230}}
* {{citation
 | last1 = Chen | first1 = Bor-Liang
 | last2 = Lih | first2 = Ko-Wei
 | doi = 10.1006/jctb.1994.1032
 | mr = 1275266
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]] | series = Series B
 | pages = 83–87
 | title = Equitable coloring of trees
 | volume = 61
 | year = 1994}}.
* {{citation
 | last1 = Chen | first1 = Bor-Liang
 | last2 = Ko | first2 = Ming-Tat
 | last3 = Lih | first3 = Ko-Wei
 | contribution = Equitable and ''m''-bounded coloring of split graphs
 | mr = 1448914
 | location = Berlin
 | pages = 1–5
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Combinatorics and Computer Science (Brest, 1995)
 | volume = 1120
 | year = 1996}}
* {{citation | doi = 10.1007/BF01895727 | last1 = Corrádi | first1 = K. | last2 = Hajnal | first2 = A. | author2-link = András Hajnal | mr = 0200185 | journal = Acta Mathematica Academiae Scientiarum Hungaricae | pages = 423–439 | title = On the maximal number of independent circuits in a graph | volume = 14 | year = 1963}}.
* {{citation | last = Erdős | first = Paul | authorlink = Paul Erdős | contribution = Problem 9 | title = Theory of Graphs and its Applications | editor-first = M. | editor-last = Fieldler | page = 159 | publisher = Czech Acad. Sci. Publ. | location = Prague | year = 1964}}.
* {{citation
 | last1 = Fellows | first1 = Michael | author1-link = Michael Fellows
 | last2 = Fomin | first2 = Fedor V.
 | last3 = Lokshtanov | first3 = Daniel
 | last4 = Rosamond | first4 = Frances
 | last5 = Saurabh | first5 = Saket
 | last6 = Szeider | first6 = Stefan
 | last7 = Thomassen | first7 = Carsten | author7-link = Carsten Thomassen
 | contribution = On the complexity of some colorful problems parameterized by treewidth
 | doi = 10.1007/978-3-540-73556-4_38
 | mr = 2397574
 | location = Berlin
 | pages = 366–377
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Combinatorial optimization and applications
 | url = http://www.ii.uib.no/~daniello/papers/COCOA-coloring.pdf
 | volume = 4616
 | year = 2007}}.
* {{citation
 | last = Furmańczyk | first = Hanna
 | mr = 2272280
 | issue = 1
 | journal = [[Opuscula Mathematica]]
 | pages = 31–44
 | title = Equitable coloring of graph products
 | url = http://www.opuscula.agh.edu.pl/vol26/1/art/opuscula_math_2603.pdf
 | volume = 26
 | year = 2006}}.
* {{citation|contribution=Proof of a conjecture of P. Erdős|first1=A.|last1=Hajnal|author1-link=András Hajnal|first2=E.|last2=Szemerédi|author2-link=Семереді Ендре|title=Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969)|publisher=North-Holland|year=1970|pages=601–623|mr=0297607}}.
* {{citation | last1 = Janson | first1 = Svante | authorlink=Svante Janson | last2 = Ruciński | first2 = Andrzej | doi = 10.1002/rsa.10031 | mr = 1900611 | issue = 3 | journal = Random Structures &Algorithms | pages = 317–342 | title = The infamous upper tail | volume = 20 | year = 2002}}.
* {{citation | last1 = Kierstead | first1 = H. A. | last2 = Kostochka | first2 = A. V. | doi = 10.1017/S0963548307008619 | mr = 2396352 | issue = 2 | journal = [[Combinatorics, Probability and Computing]] | pages = 265–270 | title = A short proof of the Hajnal-Szemerédi theorem on equitable colouring | volume = 17 | year = 2008}}
* {{citation | last1 = Komlós | first1 = János | author1-link= János Komlós (mathematician)| last2 = Sárközy | first2 = Gábor N. | last3 = Szemerédi | first3 = Endre | author3-link = Семереді Ендре | doi = 10.1007/BF01626028 | mr = 1682919 | issue = 1 | journal = Annals of Combinatorics | pages = 43–60 | title = Proof of the Seymour conjecture for large graphs | volume = 2 | year = 1998}}.
* {{citation|doi=10.2307/2319405|first=Walter|last=Meyer|title=Equitable coloring|journal=[[American Mathematical Monthly]]|volume=80|issue=8|year=1973|pages=920–922|publisher=Mathematical Association of America|jstor=2319405}}.
* {{citation | last = Pemmaraju | first = Sriram V. | contribution = Equitable colorings extend Chernoff-Hoeffding bounds | pages = 924–925 | title = Proc. 12th ACM-SIAM Symp. Discrete Algorithms (SODA 2001) | url = http://portal.acm.org/citation.cfm?id=365411.365811 | year = 2001}}.
* {{citation|first=P.|last=Seymour|authorlink=Paul Seymour (mathematician)|contribution=Problem section|title=Combinatorics: Proceedings of the British Combinatorial Conference 1973|editor1-first=T. P.|editor1-last=McDonough|editor2-first=V. C.|editor2-last=Mavron, Eds.|pages=201–202|publisher=Cambridge Univ. Press|location=Cambridge, UK|year=1974}}.
{{refend}}

{{Math-stub}}
{{Інформатика-доробити}}

[[Категорія:Розфарбування графів]]