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

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

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

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

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

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

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

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

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

Разреженность править

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

Раскраска править

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

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

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

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

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

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

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

Любой граф с числом Хадвигера k имеет максимум n2O(k log log k) клик (полных подграфов) [12].

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

Примечания править

Литература править