Справедливая окраска - Equitable coloring

В теория графов, область математики, справедливая окраска это задание цвета к вершины из неориентированный граф, таким образом, что

Никакие две соседние вершины не имеют одинаковый цвет, и
Количество вершин в любых двух цветовых классах отличается не более чем на единицу.

То есть разделение вершин по разным цветам максимально равномерное. Например, присвоение каждой вершине отдельного цвета было бы равноправным, но обычно использовалось бы намного больше цветов, чем необходимо для оптимальной равноправной окраски. Эквивалентный способ определения справедливой раскраски состоит в том, что это вложение данного графа как подграф из График Турана с тем же набором вершин. Есть два вида хроматическое число ассоциируется с ровной окраской.^[1] В справедливое хроматическое число графа грамм это наименьшее число k такой, что грамм имеет равномерный окрас с k цвета. Но грамм может не иметь равных расцветок для большего количества цветов; то справедливый хроматический порог из грамм самый маленький k такой, что грамм имеет равные раскраски для любого количества цветов, большего или равного k.^[2]

В Теорема Хайнала – Семереди, выдвинутая как гипотеза Пол Эрдёш (1964 ) и доказано Андраш Хайнал и Эндре Семереди (1970 ), утверждает, что любой граф максимальной степени Δ имеет справедливую раскраску в Δ + 1 цвет. Несколько связанных предположений остаются открытыми. Также известны алгоритмы полиномиального времени для поиска раскраски, соответствующей этой границе,^[3] и для поиска оптимальной раскраски специальных классов графов, но более общая проблема определения, имеет ли произвольный граф справедливую раскраску с заданным числом цветов, является НП-полный.

Примеры

Ровная окраска звезда K_1,5.

В звезда K_1,5 на рисунке показан полный двудольный граф, и поэтому может быть окрашен в два цвета. Однако получившаяся раскраска имеет одну вершину в одном цветовом классе и пять - в другом, и поэтому не является равномерной. Наименьшее количество цветов в равномерной раскраске этого графа - четыре, как показано на рисунке: центральная вершина должна быть единственной вершиной в своем цветовом классе, поэтому остальные пять вершин должны быть разделены по крайней мере между тремя цветовыми классами по порядку чтобы гарантировать, что все остальные классы цветов имеют не более двух вершин. В более общем смысле, Мейер (1973) замечает, что любая звезда K_1,п потребности ${ displaystyle scriptstyle 1+ lceil n / 2 rceil}$ цвета в любой однотонной расцветке; таким образом, хроматическое число графа может отличаться от его справедливого числа раскраски во столько раз, сколько п/ 4. Потому что K_1,5 имеет максимальную степень пять, количество цветов, гарантированных для него теоремой Хайнала – Семереди, равно шести, что достигается присвоением каждой вершине отдельного цвета.

Еще одно интересное явление демонстрирует другой полный двудольный граф, K_{2п + 1,2п + 1}. Этот граф имеет справедливую 2-раскраску, заданную его двудольностью. Однако он не имеет справедливой (2п + 1) -раскрашивание: любое равноправное разбиение вершин на такое количество цветовых классов должно иметь ровно две вершины на класс, но две стороны двудольного разделения не могут быть разбиты на пары, потому что они имеют нечетное количество вершин. Следовательно, справедливый хроматический порог этого графика равен 2п + 2, что значительно превышает его справедливое хроматическое число два.

Теорема Хайнала – Семереди

Теорема Брукса утверждает, что любой связный граф с максимальной степенью Δ имеет Δ-раскраску, за двумя исключениями (полные графики и нечетные циклы). Однако в целом такая окраска может быть далеко не равномерной. Пол Эрдёш (1964 ) предполагаемый что справедливая раскраска возможна только в один цвет: любой граф с максимальной степенью Δ имеет справедливую раскраску в Δ + 1 цвет. Случай Δ = 2 прост (любое объединение путей и циклов может быть равномерно окрашено с использованием повторяющегося шаблона из трех цветов с небольшими корректировками повторения при закрытии цикла) и случай Δ + 1 =п/ 3 ранее было решено Корради и Хайнал (1963). Полная гипотеза была доказана Хайнал и Семереди (1970), и теперь известна как теорема Хайнала – Семереди. Их первоначальное доказательство было длинным и сложным; более простое доказательство было дано Кирстед и Косточка (2008). Алгоритм с полиномиальным временем для нахождения равномерных раскрасок с таким количеством цветов был описан Кирстедом и Косточкой; они приписывают Марсело Мидларцу и Эндре Семереди неопубликованный ранее алгоритм полиномиального времени. Кирстед и Косточка также объявляют, но не доказывают усиление теоремы, чтобы показать, что справедливая k-раскраска существует всякий раз, когда каждые две соседние вершины имеют степени, прибавляющие не более 2k + 1.

Мейер (1973) предположил форму теоремы Брукса о справедливой раскраске: каждый связный граф с максимальной степенью Δ имеет справедливую раскраску в Δ или меньшее количество цветов, за исключением полных графов и нечетных циклов. Усиленная версия гипотезы утверждает, что каждый такой граф имеет справедливую раскраску ровно в Δ цветов, за одним дополнительным исключением: a полный двудольный граф в котором обе стороны двудольного деления имеют одинаковое нечетное число вершин.^[1]

Сеймур (1974) предложил усиление теоремы Хайнала – Семереди, которое также включает Дирак Теорема о том, что плотные графы находятся Гамильтониан: он предположил, что если каждая вершина в п-вершинный граф имеет не менее кн/(k + 1) соседей, то граф содержит в качестве подграфа граф, образованный соединением вершин, не более чем k шагов в п-цикл. Дело k = 1 - это сама теорема Дирака. Теорема Хайнала – Семереди может быть восстановлена из этой гипотезы, применяя гипотезу для больших значений k к дополнительный граф данного графа и используя в качестве классов цветов смежные подпоследовательности вершин из п-цикл. Гипотеза Сеймура приблизительно доказана, т.е.для графов, каждая вершина которых имеет не менее кн/(k + 1) + o (п) соседи.^[4] Доказательство использует несколько глубоких инструментов, включая саму теорему Хайнала – Семереди.

Еще одно обобщение теоремы Хайнала – Семереди - это гипотеза Боллобаша – Элдриджа – Катлина (или для краткости BEC-гипотеза).^[5] Это гласит, что если грамм₁ и грамм₂ графики на п вершины с максимальной степенью Δ₁ и Δ₂ соответственно, и если (Δ₁ + 1) (Δ₂ + 1) ≤ п + 1, тогда грамм₁ и грамм₂ можно упаковать. То есть, грамм₁ и грамм₂ могут быть представлены на одном и том же наборе п вершины без общих ребер. Теорема Хайнала – Семереди является частным случаем этой гипотезы, в которой грамм₂ является несвязным объединением клики. Кэтлин (1974) дает аналогичное, но более сильное условие на Δ₁ и Δ₂ при котором такая упаковка может гарантированно существовать.

Специальные классы графов

Для любого дерева с максимальной степенью Δ справедливое хроматическое число не превосходит

{ displaystyle 1+ lceil Delta / 2 rceil}

^[6]

с худшим случаем для звезды. Однако у большинства деревьев справедливое хроматическое число значительно меньше: если дерево с п вершин имеет Δ ≤п/ 3 - O (1), то он имеет равномерную раскраску всего в три цвета.^[7] Фурманчик (2006) изучает справедливое хроматическое число графические продукты.

Вычислительная сложность

Также изучалась проблема поиска равных раскрасок с минимальным количеством цветов (ниже границы Хайнала-Семереди). Прямое сокращение от раскраска графика справедливую раскраску можно доказать, добавив к графу достаточно много изолированных вершин, показав, что это НП-полный чтобы проверить, имеет ли граф равномерную раскраску с заданным количеством цветов (больше двух). Однако проблема становится более интересной, если ограничиться специальными классами графов или с точки зрения параметризованная сложность. Бодлендер и Фомин (2005) показал, что, учитывая график грамм и ряд c цветов, можно проверить, грамм допускает справедливую c-раскраска за время O (п^{O (т)}), куда т это ширина дерева из грамм; в частности, справедливая раскраска может быть решена оптимально за полиномиальное время для деревья (ранее известный из-за Чен и Лих 1994 ) и внешнепланарные графы. Алгоритм полиномиального времени также известен справедливой раскраской разделить графики.^[8] Тем не мение, Fellows et al. (2007) докажите, что, когда ширина дерева является параметром алгоритма, проблема является W [1]-сложной. Таким образом, маловероятно, что существует алгоритм полиномиального времени, независимый от этого параметра, или даже то, что зависимость от параметра может быть вынесена за пределы показателя в формуле для времени работы.

Приложения

Один из мотивов справедливого окрашивания, предложенный Мейер (1973) обеспокоенность планирование проблемы. В этом приложении вершины графа представляют собой набор задач, которые необходимо выполнить, а ребро соединяет две задачи, которые не должны выполняться одновременно. Раскраска этого графа представляет собой разбиение задач на подмножества, которые могут выполняться одновременно; таким образом, количество цветов в раскраске соответствует количеству временных шагов, необходимых для выполнения всей задачи. Из-за Балансировка нагрузки По соображениям, желательно выполнять равное или почти равное количество задач на каждом временном шаге, и это уравновешивание - именно то, что достигается равномерной окраской. Фурманчик (2006) упоминает конкретное приложение этого типа задачи планирования, распределяя университетские курсы по временным интервалам таким образом, чтобы курсы распределялись равномерно по доступным временным интервалам и избегали одновременного планирования несовместимых пар курсов.

Теорема Хайнала-Семереди также использовалась для оценки отклонение сумм случайных величин с ограниченной зависимостью (Пеммараджу 2001; Янсон и Ручиньски 2002 ). Если (как в настройке для Локальная лемма Ловаса ) каждая переменная зависит не более чем от Δ others, можно использовать справедливую раскраску графа зависимостей для разделения переменных на независимые подмножества, внутри которых Границы Чернова могут быть рассчитаны, что приведет к более жестким общим границам дисперсии, чем если бы разбиение было выполнено несправедливым образом.

Примечания

^ ^а ^б Фурманчик (2006).
^ Обратите внимание, что когда k больше, чем число вершин в графе, тем не менее существует справедливая раскраска с k цвета, в которых во всех цветовых классах есть ноль или одна вершина, поэтому каждый граф имеет равный хроматический порог.
^ Кирстед, Генри А .; Косточка, Александр В .; Мидларц, Марсело; Семереди, Эндре (17 сентября 2010 г.). «Быстрый алгоритм равномерного раскраски». Комбинаторика. 30 (2): 217–224. CiteSeerX 10.1.1.224.5588. Дои:10.1007 / s00493-010-2483-5. ISSN 0209-9683.
^ Комлос, Шаркози и Семереди (1998).
^ Боллобас и Элдридж (1978).
^ Мейер (1973).
^ Бодлендер и Гай (1983).
^ Чен, Ко и Лих (1996).

внешняя ссылка

ЭКОПТ Алгоритм Branch and Cut для решения задачи равномерного раскрашивания

[F06-1] а ^б Фурманчик (2006).

[2] Обратите внимание, что когда k больше, чем число вершин в графе, тем не менее существует справедливая раскраска с k цвета, в которых во всех цветовых классах есть ноль или одна вершина, поэтому каждый граф имеет равный хроматический порог.

[3] Кирстед, Генри А .; Косточка, Александр В .; Мидларц, Марсело; Семереди, Эндре (17 сентября 2010 г.). «Быстрый алгоритм равномерного раскраски». Комбинаторика. 30 (2): 217–224. CiteSeerX 10.1.1.224.5588. Дои:10.1007 / s00493-010-2483-5. ISSN 0209-9683.

[4] Комлос, Шаркози и Семереди (1998).

[5] Боллобас и Элдридж (1978).

[6] Мейер (1973).

[7] Бодлендер и Гай (1983).

[8] Чен, Ко и Лих (1996).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]