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

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

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

То есть распределение вершин между разными цветами будет максимально равномерным. Например, было бы справедливо присвоить каждой вершине отдельный цвет, но обычно используется гораздо больше цветов, чем необходимо для оптимальной справедливой раскраски. Эквивалентный способ определения справедливой раскраски состоит в том, что это вложение данного графа в подграф графа Турана с тем же набором вершин. Есть два типа хроматических чисел, связанных со справедливой окраской. Справедливое хроматическое число графа G — это наименьшее число k такое, что G имеет справедливую раскраску в k цветов. Но G может не иметь равноправных раскрасок для некоторого большего числа цветов; справедливый хроматический порог G G — это наименьшее k такое, что имеет справедливые раскраски для любого количества цветов , большего или равного k .

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

Примеры

Справедливая раскраска звезды К _1,5 .

Звезда полный К _1,5 — единственная центральная вершина, соединенная с пятью другими, — представляет собой двудольный граф , а потому может быть раскрашена в два цвета. Однако результирующая раскраска имеет одну вершину в одном цветовом классе и пять в другом, и поэтому не является справедливой. Наименьшее количество цветов в справедливой раскраске этого графа равно четырем: центральная вершина должна быть единственной вершиной в своем цветовом классе, поэтому остальные пять вершин должны быть разделены как минимум на три цветовых класса, чтобы гарантировать, что другой цвет все классы имеют не более двух вершин.

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

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

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

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

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

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

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

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

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

$1+\lceil \Delta /2\rceil$

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

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

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

Приложения

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

Теорема Хайнала-Семереди также использовалась для оценки дисперсии сумм случайных величин с ограниченной зависимостью ( Pemmaraju 2001 ; Janson & Ruciński 2002 ). Если (как в случае с локальной леммой Ловаса ) каждая переменная зависит не более чем от ∆ других, можно использовать справедливую раскраску графика зависимости для разделения переменных на независимые подмножества, внутри которых границы Чернова можно вычислить , что приведет к более жесткому общему результату. границы дисперсии, чем если бы разделение было выполнено несправедливым способом.

Ссылки

• Бодлендер, Ханс Л .; Фомин, Федор В. (2005), «Справедливые раскраски графов ограниченной древовидной ширины», Theoretical Computer Science , 349 (1): 22–30, doi : 10.1016/j.tcs.2005.09.027 , MR   2183465 .
• Боллобас, Б. ; Элдридж, С.Э. (1978), «Упаковки графов и приложения к вычислительной сложности», Журнал комбинаторной теории , серия B, 25 (2): 105–124, doi : 10.1016/0097-3165(78)90073-0 , MR   0511983 .
• Боллобас, Бела ; Гай, Ричард К. (1983), «Справедливая и пропорциональная раскраска деревьев», Журнал комбинаторной теории , серия B, 34 (2): 177–186, doi : 10.1016/0095-8956(83)90017-5 , MR   0703602 .
• Кэтлин, Пол А. (1974), «Подграфы графов. I.», Дискретная математика , 10 (2): 225–233, doi : 10.1016/0012-365X(74)90119-8 , MR   0357230
• Чен, Бор-Лян; Лих, Ко-Вэй (1994), «Справедливая раскраска деревьев», Журнал комбинаторной теории , серия B, 61 (1): 83–87, doi : 10.1006/jctb.1994.1032 , MR   1275266 .
• Чен, Бор-Лян; Ко, Минг-Тат; Лих, Ко-Вэй (1996), «Справедливая и m -ограниченная раскраска расщепляемых графов», Комбинаторика и информатика (Брест, 1995) , Конспект лекций по информатике, том. 1120, Берлин: Springer-Verlag, стр. 1–5, номер документа : 10.1007/3-540-61576-8_67 , ISBN.  978-3-540-61576-7 , МР   1448914
• Корради, К.; Хайнал, А. (1963), «О максимальном количестве независимых цепей в графе», Acta Mathematica Венгерской академии наук , 14 (3–4): 423–439, doi : 10.1007/BF01895727 , MR   0200185 .
• Эрдеш, Пауль (1964), «Проблема 9», Филдлер, М. (редактор), Теория графов и ее приложения , Прага: Чешская академия. наук. Изд., с. 159 .
• Товарищи, Майкл ; Фомин Федор Владимирович; Локштанов Даниил; Розамонд, Фрэнсис; Саураб, Сакет; Зейдер, Стефан ; Томассен, Карстен (2007), «О сложности некоторых красочных задач, параметризованных шириной дерева», Комбинаторная оптимизация и приложения (PDF) , Конспекты лекций по информатике, том. 4616, Берлин: Springer-Verlag, стр. 366–377, doi : 10.1007/978-3-540-73556-4_38 , ISBN.  978-3-540-73555-7 , МР   2397574 , S2CID   5621950 .
• Фурманьчик, Ханна (2006), «Справедливая раскраска графовых произведений» (PDF) , Opuscula Mathematica , 26 (1):31–44, MR   2272280 .
• Дон, А. ; Семереди, Э. (1970), «Доказательство гипотезы П. Эрдеша», Комбинаторная теория и ее приложения, II (Proc. Colloq., Balatonfüred, 1969) , Северная Голландия, стр. 601–623, МР   0297607 .
• Янсон, Сванте ; Ручинский, Анджей (2002), «Печально известный верхний хвост», Случайные структуры и алгоритмы , 20 (3): 317–342, doi : 10.1002/rsa.10031 , MR   1900611 , S2CID   8294505 .
• Кирстед, штат ХА; Косточка, А.В. (2008), «Краткое доказательство теоремы Хайнала-Семереди о справедливой раскраске», Combinatorics, Probability and Computing , 17 (2): 265–270, doi : 10.1017/S0963548307008619 , MR   2396352 , S2CID   12254683
• Комлос, Янош ; Саркози, Габор Н.; Семереди, Эндре (1998), «Доказательство гипотезы Сеймура для больших графов», Annals of Combinatorics , 2 (1): 43–60, CiteSeerX   10.1.1.122.2352 , doi : 10.1007/BF01626028 , MR   1682919 .
• Мейер, Уолтер (1973), «Справедливая раскраска», American Mathematical Monthly , 80 (8): 920–922, doi : 10.2307/2319405 , JSTOR   2319405 .
• Пеммараджу, Шрирам В. (2001), «Справедливые раскраски расширяют границы Чернова-Хеффдинга», Proc. 12-й симпозиум ACM-SIAM. Дискретные алгоритмы (SODA 2001) , Soda '01, стр. 924–925, ISBN  9780898714906 .
• Сеймур, П. (1974), «Проблемный раздел», в Макдонаф, Т.П.; Маврон, ред., ВК (ред.), Комбинаторика: материалы Британской комбинаторной конференции, 1973 г. , Кембридж, Великобритания: Cambridge Univ. Пресс, стр. 201–202 .

Внешние ссылки

• ECOPT Алгоритм ветвей и разрезов для решения задачи справедливой раскраски.