Гранди номер - Grundy number

Эта статья про жадную раскраску графов. О системе арифметики, используемой в комбинаторной теории игр, см. проворный. О ценности беспристрастной игры см. Теорема Спрага – Гранди.
Оптимальная жадная раскраска (слева) и раскраска Гранди (справа) граф короны. Цифры указывают порядок, в котором жадный алгоритм окрашивает вершины.

В теория графов, то Гранди номер или же Хроматическое число Гранди из неориентированный граф это максимальное количество цветов, которое может использовать жадная окраска стратегия, которая рассматривает вершины графа последовательно и назначает каждой вершине свой первый доступный color, используя такой порядок вершин, чтобы использовать как можно больше цветов. Номера Grundy названы в честь П. М. Гранди, который изучил аналогичную концепцию для ориентированные графы в 1939 г.[1] Ненаправленная версия была представлена Кристен и Селков (1979).[2]

Пример

Например, для граф путей с четырьмя вершинами хроматическое число равно двум, а число Гранди равно трем: если сначала окрашиваются две конечные точки пути, алгоритм жадной раскраски будет использовать три цвета для всего графа.

Атомы

Закер (2006) определяет последовательность графов, называемую т-атомы, с тем свойством, что граф имеет число Гранди не менее т тогда и только тогда, когда он содержит т-атом.Каждый т-атом образуется из независимый набор и (т − 1)-атом, добавив по одному ребру из каждой вершины (т − 1)-атом к вершине независимого множества таким образом, чтобы каждый член независимого множества имел хотя бы одно инцидентное ему ребро. т-атом можно получить, раскрасив независимое множество сначала в цвет с наименьшим номером, а затем раскрасив оставшиеся (т − 1)-атом с дополнительным т − 1 Например, единственный 1-атом - это единственная вершина, а единственный 2-атом - единственное ребро, но есть два возможных 3-атома: треугольник и путь с четырьмя вершинами.[3]

В разреженных графиках

Для графика с п вершины и вырождение d, число Гранди равно О(d бревно п). В частности, для графов ограниченного вырождения (таких как планарные графы ) или графики, для которых хроматическое число и вырождение ограничены постоянными множителями друг друга (например, хордовые графы ) число Гранди и хроматическое число находятся в пределах логарифмического множителя друг друга.[4] За интервальные графики, хроматическое число и число Гранди отличаются друг от друга в пределах 8 раз.[5]

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

Проверка того, является ли число Гранди данного графа не менее k, для фиксированной постоянной k, может выполняться в полиномиальное время, ища все возможные k-атомы, которые могут быть подграфами данного графа. Однако этот алгоритм не управляемый с фиксированными параметрами, поскольку показатель степени во времени работы зависит от k. Когда k является входной переменной, а не параметром, проблема в НП-полный.[3] Число Гранди составляет не более единицы плюс максимальная степень графа, и оно остается NP-полным, чтобы проверить, равно ли оно единице плюс максимальная степень.[6] Существует постоянная c > 1 так что это NP-жесткий при рандомизированном сокращении до приблизительный число Гранди с точностью до коэффициент аппроксимации лучше чемc.[7]

Есть точный экспоненциальное время алгоритм для числа Гранди, который выполняется во времени О(2.443п).[8]

За деревья, и графы ограниченной древовидной ширины, число Гранди может быть неограниченно большим.[9] Тем не менее, число Гранди может быть вычислено за полиномиальное время для деревьев, и его можно обрабатывать с фиксированными параметрами, если оно параметризуется как ширина дерева и число Гранди,[10] хотя (при условии гипотеза экспоненциального времени ) зависимость от ширины дерева должна быть больше одноэкспоненциальной.[8] Когда параметризовано самим числом Гранди, оно может быть вычислено за время с фиксированными параметрами для хордовые графы и графы без когтей,[8] а также (используя общие результаты по изоморфизм подграфов в разреженные графики для поиска атомов) для графов ограниченное расширение.[8][11][12]

Хорошо раскрашенные графики

Основная статья: Хорошо раскрашенный график

Граф называется хорошо окрашенный если его число Гранди равно его хроматическому числу. Проверка того, хорошо ли раскрашен график, завершена с помощью coNP.[3] В по наследству хорошо раскрашенные графики (графики, для которых каждый индуцированный подграф хорошо окрашены) точно кографы, графы, не имеющие четырехвершинного пути в качестве индуцированного подграфа.[2]

Рекомендации

  1. ^ Гранди, П.М. (1939), «Математика и игры», Эврика, 2: 6–8, архивировано с оригинал на 2007-09-27. Как цитирует Эрдеш, Пол; Hedetniemi, Stephen T .; Ласкар, Рену К.; Принс, Герт К. Э. (2003), "О равенстве частичного числа Гранди и верхнего охроматического числа графов", Дискретная математика, 272 (1): 53–64, Дои:10.1016 / S0012-365X (03) 00184-5, МИСТЕР  2019200.
  2. ^ а б Кристен, Клод А .; Сельков, Стэнли М. (1979), "Некоторые свойства совершенной окраски графов", Журнал комбинаторной теории, Серия B, 27 (1): 49–59, Дои:10.1016/0095-8956(79)90067-4, МИСТЕР  0539075.
  3. ^ а б c Закер, Манучехр (2006), "Результаты по хроматическому числу Гранди графов", Дискретная математика, 306 (23): 3166–3173, Дои:10.1016 / j.disc.2005.06.044, МИСТЕР  2273147.
  4. ^ Ирани, Сэнди (1994), "Раскраска индуктивных графиков в режиме онлайн", Алгоритмика, 11 (1): 53–72, Дои:10.1007 / BF01294263, МИСТЕР  1247988.
  5. ^ Narayanaswamy, N.S .; Субхаш Бабу, Р. (2008), "Заметка о раскраске интервальных графов по первому соответствию", Заказ, 25 (1): 49–53, Дои:10.1007 / s11083-008-9076-6, МИСТЕР  2395157.
  6. ^ Хаве, Фредерик; Сампайо, Леонардо (2010), "О Гранди числе графа", Параметризованный и точный расчет, Конспект лекций по вычисл. Наук, 6478, Springer, Berlin, pp. 170–179, Bibcode:2010LNCS.6478..170H, Дои:10.1007/978-3-642-17493-3_17, ISBN  978-3-642-17492-6, МИСТЕР  2770795.
  7. ^ Корсарз, Гай (2007), «Нижняя граница для приближения нумерации Гранди», Дискретная математика и теоретическая информатика, 9 (1).
  8. ^ а б c d Бонне, Эдуард; Фуко, Флоран; Ким, Ын Чжон; Сикора, Флориан (2015), «Сложность окраски гранди и ее варианты», Вычислительная техника и комбинаторика, Конспект лекций по вычисл. Наук, 9198, Springer, Cham, стр. 109–120, arXiv:1407.5336, Дои:10.1007/978-3-319-21398-9_9, ISBN  978-3-319-21397-2, МИСТЕР  3447246.
  9. ^ Gyárfás, A .; Лехель, Дж. (1988), "Онлайн-раскраска и раскраска графов методом первого соответствия", Журнал теории графов, 12 (2): 217–227, Дои:10.1002 / jgt.3190120212, МИСТЕР  0940831.
  10. ^ Телле, Ян Арне; Проскуровский, Анджей (1997), "Алгоритмы для задач разбиения вершин на частичных k-деревья ", Журнал SIAM по дискретной математике, 10 (4): 529–550, CiteSeerX  10.1.1.25.152, Дои:10.1137 / S0895480194275825, МИСТЕР  1477655.
  11. ^ Дворжак, Зденек; Кран, Даниэль; Томас, Робин (2010), «Определение свойств первого порядка для разреженных графов», Proc. 51-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS 2010), IEEE Computer Soc., Лос-Аламитос, Калифорния, стр. 133–142, МИСТЕР  3024787.
  12. ^ Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012), «18.3 Проблема изоморфизма подграфов и булевы запросы», Разреженность: графики, структуры и алгоритмы, Алгоритмы и комбинаторика, 28, Springer, стр. 400–401, Дои:10.1007/978-3-642-27875-4, HDL:10338.dmlcz / 143192, ISBN  978-3-642-27874-7, МИСТЕР  2920058.