Введение

Размер наибольшего полного графа, полученного сжатием ребер заданного графа.

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

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

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

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

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

Небольшая

Каждый граф с 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 имеет не более клик (полных подграфов). Определяется класс параметров графа, которые он называет S-функциями, включающими число Хадвигера. Эти функции, отображающие графы в целые числа, должны быть равны нулю для графов без ребер, быть минор-монотонными, увеличиваться на единицу при добавлении новой вершины, смежной со всеми предыдущими вершинами, и принимать большее значение из двух подграфов, разделенных разделителем клики. Множество всех таких функций образует полную решетку относительно операций поточечной минимизации и максимизации. Нижним элементом в этой решетке является число Хадвигера, а верхним элементом — ширина дерева.