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

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

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

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

  • Noga Alon, Andrzej Lingas, Martin Wahlen. Approximating the maximum clique minor and some subgraph homeomorphism problems // Theoretical Computer Science. — 2007. — Т. 374, вып. 1–3. — С. 149–158. — doi:10.1016/j.tcs.2006.12.021..
  • B. Bollobás, P. A. Catlin, Paul Erdős. Hadwiger's conjecture is true for almost every graph // European Journal of Combinatorics. — 1980. — Т. 1. — С. 195–199. — doi:10.1016/s0195-6698(80)80001-1..
  • David Eppstein. Finding large clique minors is hard // Journal of Graph Algorithms and Applications. — 2009. — Т. 13, вып. 2. — С. 197–204. — doi:10.7155/jgaa.00183. — arXiv:0807.0007..
  • Fedor V. Fomin, Sang-il Oum, Dimitrios M. Thilikos. Rank-width and tree-width of H-minor-free graphs // European Journal of Combinatorics. — 2010. — Т. 31, вып. 7. — С. 1617–1628. — doi:10.1016/j.ejc.2010.05.003. — arXiv:0910.0079..
  • Hugo Hadwiger. Über eine Klassifikation der Streckenkomplexe // Vierteljschr. Naturforsch. Ges. Zürich. — 1943. — Т. 88. — С. 133–143..
  • Rudolf Halin. S-functions for graphs // J. Geometry. — 1976. — Т. 8, вып. 1—2. — С. 171–186. — doi:10.1007/BF01917434..
  • A. V. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree // Combinatorica. — 1984. — Т. 4, вып. 4. — С. 307–316. — doi:10.1007/BF02579141..
  • Neil Robertson, Paul Seymour, Robin Thomas. Excluding infinite minors // Discrete Mathematics. — 1991. — Т. 95, вып. 1—3. — С. 303–319. — doi:10.1016/0012-365X(91)90343-Z..
  • Neil Robertson, Paul Seymour, Robin Thomas. Hadwiger's conjecture for K6-free graphs // Combinatorica. — 1993a. — Т. 13, вып. 3. — С. 279–361. — doi:10.1007/BF01202354..
  • Neil Robertson, P. D. Seymour, Robin Thomas. Linkless embeddings of graphs in 3-space // Bulletin of the American Mathematical Society. — 1993b. — Т. 28, вып. 1. — С. 84–89. — doi:10.1090/S0273-0979-1993-00335-5. — arXiv:math/9301216..
  • Andrew Thomason. The extremal function for complete minors // Journal of Combinatorial Theory. — 2001. — Т. 81, вып. 2. — С. 318–338. — doi:10.1006/jctb.2000.2013..
  • K. Wagner. Über eine Eigenschaft der ebenen Komplexe // Math. Ann.. — 1937. — Т. 114. — С. 570–590. — doi:10.1007/BF01594196..