Строительство Hajós - Hajós construction

В теория графов, раздел математики, Строительство Hajós является работа с графиками названный в честь Дьёрдь Хаджос  (1961 ), который может быть использован для построения любых критический граф или любой граф, хроматическое число есть хоть какой-то заданный порог.

Конструкция

Применение конструкции Hajós к двум экземплярам K4 путем определения вершины из каждой копии в одну вершину (показано обоими цветами), удаления ребра, инцидентного объединенной вершине в каждом подграфе (пунктир) и добавления нового ребра, соединяющего конечные точки удаленных ребер (жирный зеленый), дает то Шпиндель Мозера.

Позволять грамм и ЧАС быть двумя неориентированные графы, vw быть краем грамм, и ху быть краем ЧАС. Затем конструкция Хайоша формирует новый граф, который объединяет два графа путем определения вершин v и Икс в одну вершину, удалив два ребра vw и хуи добавив новый край wy.

Например, пусть грамм и ЧАС каждый быть полный график K4 на четырех вершинах; из-за симметрии этих графов выбор ребра для выбора из каждого из них не имеет значения. В этом случае результатом применения конструкции Хайоша является Шпиндель Мозера, семивершина график единичного расстояния для этого требуется четыре цвета.

Другой пример: если грамм и ЧАС находятся графики цикла длины п и q соответственно, то результат применения конструкции Хайоса сам является графом циклов длины п + q − 1.

Конструируемые графы

График грамм как говорят k-конструктивный (или Хаджос-k-конструируемый), когда он сформирован одним из следующих трех способов:[1]

  • Полный график Kk является k-конструируемый.
  • Позволять грамм и ЧАС быть любыми двумя k-конструируемые графы. Тогда граф, образованный применением конструкции Хайоша к грамм и ЧАС является k-конструируемый.
  • Позволять грамм быть любым k-конструируемый граф, и пусть ты и v - любые две несмежные вершины из грамм. Тогда граф, образованный объединением ты и v в одну вершину также k-конструируемый. Эквивалентно этот граф может быть сформирован добавлением ребра УФ к графику, а затем договор Это.

Связь с окраской

Несложно проверить, что каждый k-конструируемый граф требует как минимум k цвета в любых правильная раскраска графа. Действительно, для полного графа это ясно Kk, а эффект идентификации двух несмежных вершин заключается в том, чтобы заставить их иметь один и тот же цвет друг с другом в любой раскраске, что не уменьшает количество цветов. В самой конструкции Hajós новый край wy заставляет хотя бы одну из двух вершин ш и у иметь другой цвет, чем объединенная вершина для v и Икс, поэтому любая правильная раскраска объединенного графа приводит к правильной раскраске одного из двух меньших графов, из которых он был сформирован, что снова заставляет его требовать k цвета.[1]

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

Подобная конструкция может быть использована для раскраска списка вместо окраски.[4]

Конструируемость критических графов

За k = 3, каждый k-критический граф (то есть каждый нечетный цикл) может быть сгенерирован как k-конструируемый граф такой, что все графы, образованные при его построении, также являются k-критично. За k = 8, это не так: график, найденный Кэтлин (1979) как контрпример к Гипотеза Хаджоса который k-хроматические графы содержат подразделение Kk, также служит контрпримером к этой проблеме. Впоследствии k-критично, но не k-конструируемые графы исключительно через k-критические графики найдены для всех k ≥ 4. За k = 4, одним из таких примеров является график, полученный из додекаэдр граф, добавив новое ребро между каждой парой противоположный вершины[5]

Число Хаджоса

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

В частности, Мэнсфилд и валлийский (1982) определить Число Hajós час(грамм) из k-хроматический график грамм быть минимальным количеством шагов, необходимых для построения грамм из Kk, где каждый шаг формирует новый граф путем объединения двух ранее сформированных графов, слияния двух несмежных вершин ранее сформированного графа или добавления вершины или ребра к ранее сформированному графу. Они показали, что для п-вершинный граф грамм с м края, час(грамм) ≤ 2п2/3 − м + 1 − 1. Если каждый граф имеет полиномиальное число Хайоша, это будет означать, что можно доказать нераскрашиваемость в недетерминированное полиномиальное время, а значит, NP =со-НП, вывод, который считается маловероятным для теоретиков сложности.[7] Однако неизвестно, как доказать неполиномиальные нижние оценки числа Хайоша без некоторых теоретико-сложных предположений, и если бы такая оценка могла быть доказана, это также означало бы существование неполиномиальных оценок для некоторых типов Система Фреге в математическая логика.[7]

Минимальный размер дерево выражений описывающий конструкцию Хайоша для данного графа грамм может быть значительно больше, чем число Hajós грамм, потому что кратчайшее выражение для грамм может повторно использовать одни и те же графы несколько раз, экономия не разрешена в дереве выражений. Существуют 3-хроматические графы, для которых наименьшее такое дерево выражений имеет экспоненциальный размер.[8]

Другие приложения

Кестер (1991) использовал конструкцию Хайоса, чтобы сгенерировать бесконечный набор 4-критических многогранные графы, каждая из которых имеет более чем в два раза больше ребер, чем вершин. По аналогии, Лю и Чжан (2006) использовали конструкцию, начиная с График Грёча, чтобы создать множество 4-критических графы без треугольников, которые, как они показали, трудно раскрасить традиционными возврат алгоритмы.

В многогранная комбинаторика, Эйлер (2003) использовали конструкцию Hajós для генерации грани из стабильный набор многогранник.

Примечания

  1. ^ а б Дистель (2006).
  2. ^ Доказательство также можно найти в Дистель (2006).
  3. ^ Дженсен и Тофт (1994), п. 184.
  4. ^ Гравье (1996); Кубале (2004).
  5. ^ Дженсен и Ройл (1999).
  6. ^ Дистель (2006) на это ссылается, когда пишет, что последовательность операций «не всегда коротка». Дженсен и Тофт (1994), 11.6 Длина доказательств Хаджоса, стр. 184–185, ставит открытой проблему определения наименьшего числа шагов, необходимых для построения каждого п-вершинный граф.
  7. ^ а б Питасси и Уркхарт (1995).
  8. ^ Ивама и Питасси (1995).

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

  • Кэтлин, П. А. (1979), "Гипотеза Хайоша о раскраске графов: варианты и контрпримеры", Журнал комбинаторной теории, Серия B, 26: 268–274, Дои:10.1016/0095-8956(79)90062-5.
  • Дистель, Рейнхард (2006), Теория графов, Тексты для выпускников по математике, 173 (3-е изд.), Springer-Verlag, стр. 117–118, ISBN  978-3-540-26183-4.
  • Эйлер, Рейнхардт (2003), "Конструкция Хайоса и многогранники", Комбинаторная оптимизация - Эврика, ты сжимайся!, Конспект лекций по информатике, 2570, Берлин: Springer-Verlag, стр. 39–47, Дои:10.1007/3-540-36478-1_6, МИСТЕР  2163949.
  • Gravier, Sylvain (1996), "Теорема Хажоса для раскраски списка", Дискретная математика, 152 (1–3): 299–302, Дои:10.1016 / 0012-365X (95) 00350-6, МИСТЕР  1388650.
  • Хайос, Г. (1961), "Über eine Konstruktion nicht" п-färbbarer Graphen ", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Рейхе, 10: 116–117. Как цитирует Дженсен и Тофт (1994).
  • Ивама, Кадзуо; Питасси, Тониан (1995), "Экспоненциальные нижние оценки древовидного исчисления Хаджоса", Письма об обработке информации, 54 (5): 289–294, Дои:10.1016 / 0020-0190 (95) 00035-Б, МИСТЕР  1336013.
  • Дженсен, Томми Р .; Ройл, Гордон Ф. (1999), "Конструкции Hajós критических графов", Журнал теории графов, 30 (1): 37–50, Дои:10.1002 / (SICI) 1097-0118 (199901) 30: 1 <37 :: AID-JGT5> 3.0.CO; 2-В, МИСТЕР  1658542.
  • Дженсен, Томми Р .; Тофт, Бьярн (1994), Проблемы с раскраской графиков (2-е изд.), Джон Уайли и сыновья, ISBN  978-0-471-02865-9.
  • Кестер, Герхард (1991), "О 4-критических планарных графах с высокой плотностью ребер", Дискретная математика, 98 (2): 147–151, Дои:10.1016 / 0012-365X (91) 90039-5, МИСТЕР  1144633.
  • Кубале, Марек (2004), Раскраски графиков, Современная математика, 352, Американское математическое общество, стр. 156, г. ISBN  978-0-8218-3458-9.
  • Лю, Шэн; Чжан, Цзянь (2006), "Использование конструкции Хаджоса для создания экземпляров трехкратной раскраски жесткого графа", Искусственный интеллект и символические вычисления, Конспект лекций по информатике, 4120, Springer-Verlag, стр. 211–225, Дои:10.1007/11856290_19.
  • Mansfield, A.J .; Уэлш, Д. Дж. А. (1982), "Некоторые проблемы раскраски и их сложность", Теория графов (Кембридж, 1981), Северная Голландия Math. Stud., 62, Амстердам: Северная Голландия, стр. 159–170, МИСТЕР  0671913.
  • Питасси, Тониан; Уркхарт, Аласдэр (1995), "Сложность исчисления Хаджоса", Журнал SIAM по дискретной математике, 8 (3): 464–483, CiteSeerX  10.1.1.30.5879, Дои:10.1137 / S089548019224024X, МИСТЕР  1341550.