В теории графов число Хадвигера неориентированного графа 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 имеет максимум n 2 ^{O( k log log k )} клик (полных подграфов) .

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

Примечания

Литература