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

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

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

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

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

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

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

Графы с числом Хадвигера пяти менее включают верхушечные графы и вложимые без зацепления графы, оба семейства имеют полный граф K₆ среди запрещённых миноров^[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 имеет максимум n2^{O(k log log k)} клик (полных подграфов) ^[12].

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

Примечания

Литература

Эта страница в последний раз была отредактирована 10 декабря 2021 в 09:20.