Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

Примеры [ править ]

Ровная раскраска звезды К 1,5 .

Звезда К 1,5 показан на рисунке является полным двудольным графом , и , следовательно , может быть окрашена в два цвета. Однако получившаяся раскраска имеет одну вершину в одном цветовом классе и пять - в другом, и поэтому не является равномерной. Наименьшее количество цветов в равномерной раскраске этого графа - четыре, как показано на рисунке: центральная вершина должна быть единственной вершиной в своем цветовом классе, поэтому остальные пять вершин должны быть разделены по крайней мере между тремя цветовыми классами по порядку. чтобы гарантировать, что все остальные классы цветов имеют не более двух вершин. В более общем плане Мейер (1973) отмечает, что любая звезда K 1, n требуетцвета в любой однотонной расцветке; таким образом, хроматическое число графа может отличаться от его справедливого числа окраски в 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- раскраска существует всякий раз, когда каждые две соседние вершины имеют степени, добавляющие не более 2 k  + 1.

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

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

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

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

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

[6]

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

Вычислительная сложность [ править ]

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

Приложения [ править ]

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

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

Заметки [ править ]

  1. ^ а б Фурманчик (2006) .
  2. ^ Обратите внимание, что когда k больше, чем количество вершин в графе, тем не менее существует справедливая раскраска с k цветами, в которой все классы цветов имеют ноль или одну вершину в них, поэтому каждый граф имеет равный хроматический порог.
  3. ^ Кирстед, Генри А .; Косточка, Александр В .; Мидларц, Марсело; Семереди, Эндре (17 сентября 2010 г.). «Быстрый алгоритм равномерного раскраски». Combinatorica . 30 (2): 217–224. CiteSeerX  10.1.1.224.5588 . DOI : 10.1007 / s00493-010-2483-5 . ISSN  0209-9683 .
  4. ^ Комлоша, и Семереди Саркози (1998) .
  5. ^ Bollobás & Элдридж (1978) .
  6. ^ Мейер (1973) .
  7. ^ Bodlaender & Guy (1983) .
  8. ^ Chen, Ko & Лих (1996) .

Ссылки [ править ]

  • Bodlaender, Hans L .; Фомин Федор В. (2005), "Равные раскрасок графов ограниченных древесной ширины", Теоретическая информатика , 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), "Равная и пропорциональная окраска дерев", Журнал комбинаторной теории , Series B, 34 (2): 177-186, DOI : 10,1016 / 0095-8956 (83) 90017-5 , М.Р.  0703602.
  • Кэтлин, Пол А. (1974), "Подграфы графов. I.", Дискретная математика. , 10 (2): 225-233, DOI : 10.1016 / 0012-365X (74) 90119-8 , МР  0357230
  • Чен, Бор-Лян; Лих, Ко-Вэй (1994), "Равный окраски деревьев", Журнал комбинаторной теории , Series B, 61 (1): 83-87, DOI : 10,1006 / jctb.1994.1032 , МР  1275266.
  • Чен, Бор-Лян; Ко, Мин-Тат; Лих, Ко-Вей (1996), "Справедливая и m- ограниченная раскраска расщепленных графов", Комбинаторика и информатика (Брест, 1995) , Конспект лекций по компьютерным наукам, 1120 , Берлин: Springer-Verlag, стр. 1–5 , DOI : 10.1007 / 3-540-61576-8_67 , ISBN 978-3-540-61576-7, MR  1448914
  • Corrádi, K .; Hajnal, А. (1963), "О максимальном количестве независимых контуров в графе", Acta Mathematica Academiae Scientiarum Hungaricae , 14 (3-4): 423-439, DOI : 10.1007 / BF01895727 , МР  0200185.
  • Эрдеш, Пауль (1964), «Проблема 9», Филдлер, М. (ред.), Теория графов и ее приложения , Прага: Czech Acad. Sci. Publ., Стр. 159.
  • Товарищи, Майкл ; Фомин, Федор В .; Локштанов Даниил; Розамонд, Фрэнсис; Саураб, Сакет; Шейдер, Стефан ; Томассен, Карстен (2007), «О сложности некоторых красочных задач, параметризованных шириной дерева», Комбинаторная оптимизация и приложения (PDF) , Lecture Notes in Computer Science, 4616 , Berlin: Springer-Verlag, pp. 366–377, doi : 10.1007 / 978-3-540-73556-4_38 , ISBN 978-3-540-73555-7, Руководство по ремонту  2397574.
  • Фурманчик, Ханна (2006), «Справедливая раскраска графических произведений» (PDF) , Opuscula Mathematica , 26 (1): 31–44, MR  2272280.
  • Хайнал, А .; Семереди, Э. (1970), "Доказательство гипотезы П. Эрдеша", Комбинаторная теория и ее приложения, II (Proc. Colloq., Balatonfüred, 1969) , North-Holland, стр. 601–623, MR  0297607.
  • Янсон, Сванте ; Ruciński, Анджей (2002), "Позорный верхний хвост", Случайные структуры и алгоритмы , 20 (3): 317-342, DOI : 10.1002 / rsa.10031 , МР  1900611.
  • Кирстед, штат Джорджия; Косточка, А. В. (2008), "Короткое доказательство теоремы Hajnal-Семереди на равноправной раскраске", Комбинаторика, Вероятность и вычисления , 17 (2): 265-270, DOI : 10,1017 / S0963548307008619 , MR  2396352
  • Комлос, Янош ; Шаркози, Габор Н .; Семереди, Эндре (1998), "Доказательство гипотезы Сеймура для больших графов", Анналы Комбинаторика , 2 (1): 43-60, CiteSeerX  10.1.1.122.2352 , DOI : 10.1007 / BF01626028 , МР  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), «Проблемный раздел», в McDonough, TP; Mavron, Eds., VC (eds.), Combinatorics: Proceedings of the British Combinatorial Conference 1973 , Cambridge, UK: Cambridge Univ. Press, стр. 201–202..

Внешние ссылки [ править ]

  • ECOPT A Branch and Cut алгоритм для решения задачи равномерного раскрашивания