В теории графов , то Гранди номер или Гранди хроматическое число из неориентированного графа максимального количества цветов , которые могут быть использованы с помощью жадной красящей стратегии , которая учитывает вершину графа в последовательности и присваивает каждую вершину ее первый доступный цвет, используя порядок вершин выбран так, чтобы использовать как можно больше цветов. Числа Гранди названы в честь П.М. Гранди , который изучал аналогичную концепцию для ориентированных графов в 1939 году. [1] Ненаправленная версия была введена Кристеном и Селковом (1979) . [2]
Пример [ править ]
Например, для графа путей с четырьмя вершинами хроматическое число равно двум, а число Гранди равно трем: если сначала окрашиваются две конечные точки пути, алгоритм жадной раскраски будет использовать три цвета для всего графа.
Атомы [ править ]
Закер (2006) определяет последовательность графов , называемых т - атомы , со свойством , что граф имеет Гранди число , по меньшей мере т тогда и только тогда , когда она содержит т -атом. Каждый t -атом формируется из независимого набора и ( t - 1) -атома путем добавления одного ребра из каждой вершины ( t - 1) -атома к вершине независимого набора таким образом, чтобы каждый член независимого множества имеет хотя бы одно инцидентное ему ребро. Гранди раскраска t-атом может быть получен путем окраски независимого множества сначала в цвет с наименьшим номером, а затем окраски оставшегося ( t - 1) -атома дополнительными t - 1 цветами. Например, единственный 1-атом - это единственная вершина, а единственный 2-атом - единственное ребро, но есть два возможных 3-атома: треугольник и путь с четырьмя вершинами. [3]
В разреженных графиках [ править ]
Для графа с n вершинами и вырожденностью d число Гранди равно O ( d log n ) . В частности, для графов с ограниченным вырождением (таких как плоские графы ) или графов, для которых хроматическое число и вырождение ограничены постоянными множителями друг друга (например, хордовые графы ), число Гранди и хроматическое число находятся в пределах логарифмического множителя каждого Другой. [4] Для интервальных графиков хроматическое число и число Гранди находятся в пределах 8 раз друг от друга. [5]
Вычислительная сложность [ править ]
Проверка того, что число Гранди данного графа не меньше k для фиксированной константы k , может быть выполнено за полиномиальное время путем поиска всех возможных k -атомов, которые могут быть подграфами данного графа. Однако этот алгоритм не является управляемым с фиксированными параметрами , потому что показатель степени во времени его работы зависит от k . Когда k является входной переменной, а не параметром, проблема NP-полная . [3] Число Гранди составляет не более единицы плюс максимальная степень графа, и оно остается NP-полным, чтобы проверить, равно ли оно единице плюс максимальная степень. [6] Существует постояннаяc > 1 , так чтопри рандомизированных редукциях NP-сложно аппроксимировать число Гранди с точностью до отношения приближения лучше, чем c . [7]
Существует алгоритм точного экспоненциального времени для числа Гранди, который выполняется за время O (2.443 n ) . [8]
Для деревьев и графов с ограниченной древесной шириной число Гранди может быть неограниченно большим. [9] Тем не менее, число Гранди может быть вычислено за полиномиальное время для деревьев и является управляемым с фиксированным параметром, если параметризовано как шириной дерева, так и числом Гранди, [10] хотя (при допущении гипотезы экспоненциального времени ) зависимость от ширины дерева должна быть больше, чем однократно экспоненциальный. [8] Когда параметризовано самим числом Гранди, оно может быть вычислено за время с фиксированными параметрами для хордовых графов и графов без клешней , [8] а также (с использованием общих результатов поизоморфизм подграфов в разреженных графах для поиска атомов) для графов ограниченного расширения . [8] [11] [12]
Хорошо раскрашенные графики [ править ]
Граф называется хорошо раскрашенным, если его число Гранди равно его хроматическому числу. Проверка того, хорошо ли раскрашен график, завершена с помощью coNP. [3] В наследственно хорошо цветных графиках (графики , для которых каждый подграф хорошо цвет) в точности cographs , графики , которые не имеют пути четыре вершины в качестве индуцированного подграфа. [2]
Ссылки [ править ]
- ^ Гранди, PM (1939), "Математика и игры" , Eureka , 2 : 6-8, архивируются с оригинала на 2007-09-27. Цитируется Erdős, Paul ; Hedetniemi, Stephen T .; Laskar, Renu C .; Принс, Герт CE (2003), «О равенстве частичного числа Гранди и верхнего охроматического числа графов», Дискретная математика , 272 (1): 53–64, DOI : 10.1016 / S0012-365X (03) 00184-5 , MR 2019200 .
- ^ a b Кристен, Клод А .; Сельков, Стэнли М. (1979), "Некоторые свойства идеальной раскраски графов", Журнал комбинаторной теории , серия B, 27 (1): 49–59, DOI : 10.1016 / 0095-8956 (79) 90067-4 , MR 0539075 .
- ^ Б с Закер Манучехр (2006), "Результаты по Grundy хроматического числа графов", дискретной математики , 306 (23): 3166-3173, DOI : 10.1016 / j.disc.2005.06.044 , МР 2273147 .
- ^ Ирани, Сэнди (1994), "Окрашивание индуктивных график он-лайн", Algorithmica , 11 (1): 53-72, DOI : 10.1007 / BF01294263 , МР 1247988 .
- ^ Нараянасвами, NS; Subhash Баба, R. (2008), "Записка о первой подгонке раскраске графов интервалов", Order , 25 (1): 49-53, DOI : 10.1007 / s11083-008-9076-6 , MR 2395157 .
- ^ Хаве, Фредерик; Сампайо, Леонардо (2010), «О Гранди-числе графа», Параметризованные и точные вычисления , Конспекты лекций в Comput. Sci . , 6478 , Springer, Berlin, стр 170-179,. Bibcode : 2010LNCS.6478..170H , DOI : 10.1007 / 978-3-642-17493-3_17 , ISBN 978-3-642-17492-6, Руководство по ремонту 2770795.
- ^ Корсарц, Гай (2007), "Нижняя оценка для аппроксимации нумерации Гранди" , Дискретная математика и теоретическая информатика , 9 (1).
- ^ a b c d Бонне, Эдуард; Фуко, Флоран; Ким, Ын Чжон; Сикора, Флориан (2015), «Сложность раскраски Гранди и ее варианты», Вычислительная техника и комбинаторика , Конспект лекций в Comput. Наук,. 9198 , М., Чам, стр 109-120,. Arxiv : 1407.5336 , DOI : 10.1007 / 978-3-319-21398-9_9 , ISBN 978-3-319-21397-2, Руководство по ремонту 3447246.
- ^ Gyárfás, A .; Леэль, J. (1988), "он-лайн и в первую очередь установить раскраски графов", Журнал теории графов , 12 (2): 217-227, DOI : 10,1002 / jgt.3190120212 , МР 0940831 .
- ^ Телле, Ян Арне; Proskurowski, Анджей (1997), "Алгоритмы для задач разбиения вершин на частичном K -дерев", SIAM журнал по дискретной математике , 10 (4): 529-550, CiteSeerX 10.1.1.25.152 , DOI : 10,1137 / S0895480194275825 , МР 1477655 .
- ^ Дворжак, Зденек ; Krá, Daniel ; Томас, Робин (2010), "Определение свойств первого порядка для разреженных графов", Proc. 51-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS 2010) , IEEE Computer Soc., Лос-Аламитос, Калифорния, стр. 133–142, MR 3024787 .
- ^ Нешетржил, Ярослав ; Ossona де Мендес, Патрис (2012), "18,3 подграф Изоморфизм Проблемы и Boolean Запросы", разреженность: Графики, структура и алгоритмы , алгоритмы и комбинаторика, 28 , Springer, стр 400-401,. Дои : 10.1007 / 978-3 -642-27875-4 , ЛВП : 10338.dmlcz / 143192 , ISBN 978-3-642-27874-7, MR 2920058.
