Введение
Максимальное количество цветов, которые можно получить алгоритмом окрашивания графа с жадностью жадное окрашивание графов В теории графов число Гранди или хроматическое число Гранди ненаправленного графа - это максимальное количество цветов, которые могут быть использованы стратегией окрашивания с жадностью, которая рассматривает вершины графа в последовательности и присваивает каждой вершине ее первый доступный цвет, используя упорядочение вершин, выбранное для использования как можно большего количества цветов. Числа Гранди названы в честь П. М. Гранди, который изучил аналогичную концепцию для направленных графов в 1939 году. Ненаправленная версия была введена .
greedy coloring of graphs
In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. The undirected version was introduced by .
Примеры
График пути с четырьмя вершинами представляет собой самый простой пример графа, чье хроматическое число отличается от числа Грунди. Этот график может быть окрашен в два цвета, но его число Грунди равняется трем: если сначала окрасить две конечные точки пути, то алгоритм окрашивания использует три цвета для всего графика.
Атомы
определяет последовательность графов, называемых t атомами, с свойством, что граф имеет число Гранди по крайней мере t, если и только если он содержит t атома. Каждый атом t образуется из независимого множества и атома a (t - 1), добавляя один край от каждой вершины атома (t - 1) к вершине независимого множества таким образом, что каждый член независимого множества имеет по крайней мере один край, приходящийся на него. Цвет Гранди атома t можно получить, окрасив сначала независимое множество наименьшим пронумерованным цветом, а затем окрасив оставшийся (t − 1) атом дополнительным цветом t − 1. Например, только 1 атом является одной вершиной, и только 2 атома - это один край, но есть два возможных 3 атома: треугольник и путь четырех вершин. Для интервальных графиков хроматическое число и число Гранди находятся в пределах 8 друг от друга.
Комплексность вычислений
Испытание того, равно ли число Гранди данного графа по меньшей мере k, для фиксированной константы k, может быть выполнено в полиномиальное время, путем поиска всех возможных k атомов, которые могут быть подграфами данного графа. Однако этот алгоритм не является фиксированным параметром, потому что показатель в его времени выполнения зависит от k. Когда k является входной переменной, а не параметром, задача NP-полная. Число Гранди составляет максимум один плюс максимальная степень графика, и оно остается NP полным, чтобы проверить, равно ли оно одному плюс максимальная степень. Существует постоянная c > 1, так что NP трудно при рандомизированных уменьшениях приблизить число Гранди в пределах соотношения приближения лучше, чем c. Существует точный алгоритм экспоненциального времени для числа Гранди, который работает во времени O ((2.443 ^ ((n)). Тем не менее, число Гранди может быть вычислено в полиномиальном времени для деревьев, и является фиксированным параметром, обратимым, когда параметрируется как по ширине дерева, так и по числу Гранди, хотя (принимая гипотезу экспоненциального времени) зависимость от ширины дерева должна быть больше, чем отдельно экспоненциальная. а также (используя общие результаты по изоморфизму подграфов в разреженных графах для поиска атомов) для графов ограниченного расширения. Однако на общих графах задача W[1] является жесткой, когда параметризируется числом Гранди.
There is an exact exponential time algorithm for the Grundy number that runs in time O(2.443^(n)). Nevertheless, the Grundy number can be computed in polynomial time for trees,
and is fixed parameter tractable when parameterized by both the treewidth and the Grundy number, although (assuming the exponential time hypothesis) the dependence on treewidth must be greater than singly exponential. and also (using general results on subgraph isomorphism in sparse graphs to search for atoms) for graphs of bounded expansion. However, on general graphs the problem is W[1] hard when parameterized by the Grundy number.
Яркие цветные графики
Граф называется хорошо окрашенным, если его число Грунди равно его хроматическому числу. Испытание того, хорошо ли окрашен график, завершено. Наследственно хорошо окрашенные графы (графы, для которых каждый индуцированный подграф хорошо окрашен) являются именно кографами, графами, которые не имеют четырех вершинного пути в качестве индуцированного подграфа.