Число Хадвигера

Граф с четырьмя связными подграфами, которые, после стягивания, образуют полный граф. Согласно теореме Вагнера граф не имеет пятивершинного полного минора, так что число Хадвигераэтого графа равно четырём.

В теории графов число Хадвигера неориентированного графа G — это размер наибольшего полного графа, который может быть получен стягиванием рёбер графа G. Эквивалентно, число Хадвигера h(G) — это наибольшее число k, для которого полный граф K_k является минором графа G, меньший граф, полученный из G стягиванием рёбер и удалением вершин и рёбер. Число Хадвигера известно также как число кликового стягивания графа G или степень гомоморфизма графа G. Число названо именем Гуго Хадвигера, который ввёл число в 1943 и высказал гипотезу, по которой число Хадвигера всегда не меньше хроматического числа графа G.

Графы, имеющие число Хадвигера 4 и менее, описаны Вагнером. Графы с любым конечным числом Хадвигера разрежены и имеют малое хроматическое число. Определение числа Хадвигера для графа является NP-трудной задачей, но задача фиксированно-параметрически разрешима.

Графы с малым число Хадвигера

Граф G имеет число Хадвигера не более 2 тогда и только тогда, когда он является лесом, а трёхвершинный полный минор может быть образован стягиванием цикла в G.

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

Сумма по кликам двух планарных графов и графа Вагнера даёт граф с числом Хадвигера, равным четырём.

Из теоремы Вагнера, описывающей планарные графы их запрещёнными подграфами, следует, что планарные графы имеют число Хадвигера, не превосходящее 4. В некоторых статьях, содержащих доказательство теоремы, Вагнер описывает графы с числом Хадвигера четыре и менее более точно — это графы, которые можно образовать с помощью операций сумма по клике планарных графов с графом Вагнера, имеющим 8 вершин.

Графы с числом Хадвигера пяти менее включают верхушечные графы и вложимые без зацепления графы, оба семейства имеют полный граф K₆ среди запрещённых миноров

Разреженность

Любой граф с n вершинами и числом Хадвигера k имеет O(nk √log k) рёбер. Эта граница точна — для любого k существует граф с числом Хадвигера k, имеющий Ω(nk √log k) рёбер . Если граф G имеет число Хадвигера k, то все его подграфы также имеют число Хадвигера, не превосходящее k, и отсюда следует, что граф G должен иметь вырожденность O(k √log k). Таким образом, графы с ограниченным числом Хадвигера являются разреженными графами.

Раскраска

Гипотеза Хадвигера утверждает, что число Хадвигера всегда не меньше хроматического числа графа G. То есть любой граф с числом Хадвигера k должен бы иметь раскраску в максимум k цветов. Случай k = 4 эквивалентен (по характеризации Вагнера графов с этим числом Хадвигера) задаче четырёх красок о раскраске планарных графов. Гипотеза доказана также для k ≤ 5, но остаётся недоказанной для больших значений k

Ввиду низкой плотности графы с числом Хадвигера, не превосходящим k, могут быть раскрашены с помощью алгоритма жадной раскраски в O(k √log k) цветов.

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

Проверка, не превосходит ли число Хадвигера данного графа некоторого значения k, является NP-полной задачей, откуда следует, что определение числа Хадвигера является NP-трудной задачей. Тем не менее, задача фиксированно-параметрически разрешима — существует алгоритм определения наибольшего кликового минора за время, зависящее лишь полиномиально от размера графа, но экспоненциально от h(G) . Кроме того, алгоритмы полиномиального времени могут аппроксимировать число Хадвигера существенно точнее, чем лучшая полиномиального времени аппроксимация (в предположении, что P ≠ NP) размера наибольших полных подграфов.

Связанные понятия

Ахроматическое число графа G — это размер наибольшей клики, которую можно образовать путём стягивания семейства независимых множеств в G.

Несчётные кликовые миноры в бесконечных графах можно охарактеризовать в терминах укрытий, которые формализуют стратегии уклонения для некоторых игр преследования-уклонения — если число Хадвигера несчётно, оно равно порядку наибольшего убежища в графе .

Любой граф с числом Хадвигера k имеет максимум n2^{O(k log log k)} клик (полных подграфов) .

Халин определил класс параметров графа, которые он назвал S-функциями. Среди них есть и число Хадвигера. Требуется, чтобы эти функции, отображающие графы в целые числа, принимали нулевое значение на графах без рёбер, были минорно монотонными, требуется увеличение на единицу при добавлении новой вершины, смежной со всеми предыдущими вершинами, и из двух значений для подграфов по обеим сторонам сепаратора клик функция должна принимать большее значение. Множество таких функций образует полную решётку по операциям взятия минимального или максимального элементов. Нижний элемент в такой решётке является числом Хадвигера, а верхний элемент — древесная ширина.