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

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

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

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

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

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

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

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

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

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

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

Каждый график с п вершины и число Хадвигера k имеет O (нк √бревно k) края. Эта граница жесткая: для каждого k, существуют графы с числом Хадвигера k которые имеют Ω (нк √бревно k) края.[4] Если график грамм имеет номер Хадвигера k, то все его подграфы также имеют число Хадвигера не более k, откуда следует, что грамм должны быть вырождение O (k √бревно k). Следовательно, графы с ограниченным числом Хадвигера являются разреженные графики.

Окраска

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

Графы с числом Хадвигера не более k может быть раскрашен жадная окраска алгоритм с использованием O (k √бревно k) цвета.

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

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

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

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

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

Каждый график с числом Хадвигера k имеет самое большее п2O (k журнал журналk) клики (полные подграфы).[9]

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

Примечания

  1. ^ Боллобас, Катлин и Эрдеш (1980).
  2. ^ Халин (1976).
  3. ^ Робертсон, Сеймур и Томас (1993b).
  4. ^ Косточка (1984); Томасон (2001). Буквы O и Ω в этих выражениях вызывают нотация большой O.
  5. ^ Робертсон, Сеймур и Томас (1993a).
  6. ^ Эппштейн (2009).
  7. ^ а б Алон, Лингас и Вален (2007)
  8. ^ Робертсон, Сеймур и Томас (1991).
  9. ^ Фомин, Оум и Тиликос (2010).
  10. ^ Если функция ж минорно-монотонный, то если ЧАС является несовершеннолетним из грамм тогда f (H) ≤ f (G).

Рекомендации