Число Гранди

Максимальное количество цветов, которое можно получить с помощью жадного алгоритма раскраски графа

Оптимальная жадная раскраска (слева) и раскраска Гранди (справа) графа короны . Числа указывают порядок, в котором жадный алгоритм раскрашивает вершины.

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

Примеры

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

Полные двудольные графы являются единственными связными графами, число Гранди которых равно двум. Все остальные связные графы содержат либо треугольник, либо путь из четырех вершин, что приводит к тому, что число Гранди становится не менее трех. ^[3]

Графы короны получаются из полных двудольных графов путем удаления идеального соответствия . В результате для каждой вершины на одной стороне двудольного графа существует ровно одна вершина на противоположной стороне двудольного графа, с которой она не соседствует. Как двудольные графы, они могут быть раскрашены двумя цветами, но их число Гранди равно : если жадный алгоритм раскраски рассматривает каждую сопоставленную пару вершин по порядку, каждая пара получит свой цвет. Как показывает этот пример, число Гранди может быть больше хроматического числа на коэффициент, линейный по количеству вершин графа. ^[4] ${\displaystyle K_{n,n}}$ ${\displaystyle n}$

Атомы

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

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

Для графа с n вершинами и вырожденностью d число Гранди равно O ( d log n ) . В частности, для графов ограниченной вырожденности (таких как планарные графы ) или графов, для которых хроматическое число и вырожденность ограничены в пределах постоянных множителей друг от друга (таких как хордовые графы ), число Гранди и хроматическое число находятся в пределах логарифмического множителя друг от друга. ^[5] Для интервальных графов хроматическое число и число Гранди находятся в пределах множителя 8 друг от друга. ^[6]

Сложность вычислений

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

Существует точный экспоненциальный алгоритм для числа Гранди, который выполняется за время O (2,443 ⁿ ) . ^[9]

Для деревьев и графов ограниченной древовидной ширины число Гранди может быть неограниченно большим. ^[10] Тем не менее, число Гранди может быть вычислено за полиномиальное время для деревьев и является поддающимся обработке с фиксированными параметрами, если параметризовано как древовидной шириной, так и числом Гранди, ^[11] хотя (предполагая гипотезу экспоненциального времени ) зависимость от древовидной ширины должна быть больше, чем просто экспоненциальная. ^[9] При параметризации только числом Гранди его можно вычислить за поддающееся обработке время с фиксированными параметрами для хордовых графов и графов без клешней , ^[9] а также (используя общие результаты по изоморфизму подграфов в разреженных графах для поиска атомов) для графов ограниченного расширения . ^{[9] [12] [13]} Однако на общих графах задача является W[1]-трудной, если параметризована числом Гранди. ^[14]

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

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

Ссылки

1. Grundy, PM (1939), «Математика и игры», Eureka , 2 : 6–8, архивировано из оригинала 27 сентября 2007 г.. Как цитируется Эрдёшем, Полом ; Хедетниеми, Стивеном Т.; Ласкар, Рену К.; Принсом, Гертом CE (2003), «О равенстве парциального числа Гранди и верхнего охроматического числа графов», Дискретная математика , 272 (1): 53–64, doi : 10.1016/S0012-365X(03)00184-5 , MR  2019200.
2. Christen, Claude A.; Selkow, Stanley M. (1979), "Некоторые свойства идеальной раскраски графов", Journal of Combinatori Theory , Series B, 27 (1): 49–59, doi : 10.1016/0095-8956(79)90067-4 , MR  0539075.
3. Закер, Манучехр (2006), «Результаты по хроматическому числу Гранди графов», Дискретная математика , 306 (23): 3166–3173, doi : 10.1016/j.disc.2005.06.044 , MR  2273147.
4. Джонсон, Д.С. (1974), «Поведение алгоритмов раскраски графов в наихудшем случае», Труды 5-й Юго-восточной конференции по комбинаторике, теории графов и вычислениям, Utilitas Mathematicae , Виннипег, стр. 513–527, MR  0389644{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
5. Ирани, Сэнди (1994), «Раскраска индуктивных графов в режиме онлайн», Algorithmica , 11 (1): 53–72, doi :10.1007/BF01294263, MR  1247988, S2CID  181800.
6. Нараянасвами, Н. С.; Субхаш Бабу, Р. (2008), «Заметка о первой подходящей раскраске интервальных графов», Order , 25 (1): 49–53, doi :10.1007/s11083-008-9076-6, MR  2395157, S2CID  207223738.
7. Хаве, Фредерик; Сампайо, Леонардо (2010), «О числе Гранди графа», Параметризованные и точные вычисления , Lecture Notes in Comput. Sci., т. 6478, Springer, Берлин, стр. 170–179, Bibcode : 2010LNCS.6478..170H, doi : 10.1007/978-3-642-17493-3_17, ISBN 978-3-642-17492-6, МР  2770795.
8. Кортсарц, Гай (2007), «Нижняя граница для аппроксимации нумерации Гранди», Дискретная математика и теоретическая информатика , 9 (1).
9. Бонне, Эдуард; Фуко, Флоран; Ким, Ын Чжон ; Сикора, Флориан (2015), «Сложность раскраски Гранди и ее варианты», Вычислительная техника и комбинаторика , Lecture Notes in Comput. Sci., т. 9198, Springer, Cham, стр. 109–120, arXiv : 1407.5336 , doi : 10.1007/978-3-319-21398-9_9, ISBN 978-3-319-21397-2, MR  3447246, S2CID  5514223.
10. Gyárfás, A.; Lehel, J. (1988), «Онлайн и первая подходящая раскраска графов», Журнал теории графов , 12 (2): 217–227, doi :10.1002/jgt.3190120212, MR  0940831, S2CID  8839035.
11. Телле, Ян Арне; Проскуровски, Анджей (1997), «Алгоритмы для задач разбиения вершин на частичных k- деревьях», SIAM Journal on Discrete Mathematics , 10 (4): 529–550, CiteSeerX 10.1.1.25.152 , doi :10.1137/S0895480194275825, MR  1477655 .
12. Дворжак, Зденек ; Краль, Даниэль ; Томас, Робин (2010), «Определение свойств первого порядка для разреженных графов», Труды 51-го ежегодного симпозиума IEEE по основам компьютерной науки (FOCS 2010) , IEEE Computer Soc., Лос-Аламитос, Калифорния, стр. 133–142, MR  3024787.
13. Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «18.3 Проблема изоморфизма подграфов и булевы запросы», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, т. 28, Springer, стр. 400–401, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МР  2920058.
14. Абулкер, Пьер; Бонне, Эдуард; Ким, Ын Чжон; Сикора, Флориан (2023), «Раскраска Гранди и друзья, полуграфы, биклики», Algorithmica , 85 : 1–28, doi :10.1007/s00453-022-01001-2, S2CID  250614665.