Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Коготь

В теории графов , области математики, граф без когтей - это граф, у которого нет когтей в качестве индуцированного подграфа .

Коготь - это другое название полного двудольного графа K 1,3 (то есть звездного графа с тремя ребрами, тремя листами и одной центральной вершиной). Граф без клешней - это граф, в котором ни один индуцированный подграф не является клешней; т.е. любое подмножество из четырех вершин имеет не только три ребра, соединяющие их в этом шаблоне. Эквивалентно, граф без клешней - это граф, в котором окрестность любой вершины является дополнением к графу без треугольников .

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

Примеры [ править ]

Правильный икосаэдр, многогранник, вершины и ребра которого образуют граф без клешней.
  • Линейный график L ( G ) любой граф G является зубчатым свободным; L ( G ) имеет вершину для каждого ребра G , и вершины смежны в L ( G ) всякий раз , когда соответствующие ребра разделяют конечную точку в G . Линейный граф L ( G ) не может содержать клешню, потому что, если все три ребра e 1 , e 2 и e 3 в G имеют общие конечные точки с другим ребром e 4, то по принципу ячейкипо крайней мере два из e 1 , e 2 и e 3 должны совместно использовать одну из этих конечных точек друг с другом. Линейные графы можно охарактеризовать с помощью девяти запрещенных подграфов; [2] клешня - самый простой из этих девяти графов. Эта характеристика послужила первоначальной мотивацией для изучения графов без клешней. [1]
  • В графах де Брейно (графы, вершины представляют собой п -битового двоичных строк для некоторого п , а ребра представляют собой ( п  - 1) -битовым перекрываются между двумя строками) являются зубчатыми бесплатно. Один из способов показать это - построить граф де Брейна для n- битных строк как линейный граф графа де Брейна для ( n  - 1) -битных строк.
  • Дополнение любого треугольника свободного графика является когтем бесплатно. [3] Эти графы включают как частный случай любой полный граф .
  • Правильные интервальные графы , интервальные графы, сформированные как графы пересечений семейств интервалов, в которых ни один интервал не содержит другого интервала, не имеют когтей, потому что четыре правильно пересекающихся интервала не могут пересекаться в образце когтя. [3] То же самое в более общем случае верно для правильных графов дуги окружности . [4]
  • Moser шпиндель , семь вершин графа используется , чтобы обеспечить нижнюю границу для хроматического числа плоскости , является зубчатыми свободным.
  • Графики нескольких многогранников и многогранников являются зубчатыми свободным, в том числе графика тетраэдра и в более общем плане любого симплекса (полный граф), в графу октаэдра и в более общем плане любого поперечного многогранника ( изоморфно к коктейль графу , образованному путь удаления полного совпадения из полного графа), график регулярного икосаэдре , [5] и графика 16-клетки .
  • Граф Шлефли , сильно регулярный граф с 27 вершинами, не имеет клешней. [5]

Признание [ править ]

Несложно проверить, что данный граф с n вершинами и m ребрами свободен от когтей за время O ( n 4 ), проверяя каждый набор из 4 вершин, чтобы определить, порождают ли они когти. [6] С большей эффективностью и большей сложностью можно проверить, свободен ли граф от когтей, проверив для каждой вершины графа, что дополнительный граф его соседей не содержит треугольника. Граф содержит треугольник тогда и только тогда, когда куб его матрицы смежности содержит ненулевой диагональный элемент, поэтому поиск треугольника может быть выполнен за ту же асимптотическую границу времени, что и n  ×  n. матричное умножение . [7] Следовательно, при использовании алгоритма Копперсмита – Винограда общее время для этого алгоритма распознавания без когтей будет O ( n 3,376 ).

Kloks, Kratsch & Müller (2000) отмечают, что в любом графе без клешней каждая вершина имеет не более 2 √ m соседей; в противном случае по теореме Турана у соседей вершины не было бы достаточно оставшихся ребер, чтобы образовать дополнение графа без треугольников. Это наблюдение позволяет выполнять проверку каждой окрестности в алгоритме, основанном на быстром умножении матриц, описанном выше, с той же асимптотической временной границей, что и умножение матриц 2 √ m  × 2 √ m , или быстрее для вершин с еще более низкими степенями. Наихудший случай для этого алгоритма имеет место, когда вершины Ω ( √ m ) имеют Ω ( √ m) соседствует каждая, а остальные вершины имеют несколько соседей, поэтому общее время составляет O ( m 3,376 / 2 ) = O ( m 1,688 ).

Перечисление [ править ]

Поскольку графы без клешней включают дополнения к графам без треугольников, количество графов без клешней на n вершинах растет, по крайней мере, так же быстро, как количество графов без треугольников, экспоненциально в квадрате n . Количество связных графов без клешней на n узлах для n  = 1, 2, ... равно

1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, ... (последовательность A022562 в OEIS ).

Если графы могут быть отключены, количество графов еще больше: они

1, 2, 4, 10, 26, 85, 302, 1285, 6170, ... (последовательность A086991 в OEIS ).

Методика Палмера, Рида и Робинсона (2002) позволяет очень эффективно подсчитывать количество кубических графов без клешней , что необычно для задач перечисления графов .

Соответствия [ править ]

Доказательство Самнера, что связные графы четного порядка без клешней имеют идеальные паросочетания: удаление двух соседних вершин v и w , наиболее удаленных от u, оставляет связный подграф, внутри которого может быть повторен тот же процесс удаления.

Самнер (1974) и, независимо, Лас Вергнас (1975) доказали, что любой связный граф без когтей с четным числом вершин имеет идеальное соответствие . [8] То есть существует такой набор ребер в графе, что каждая вершина является конечной точкой ровно одного из совпадающих ребер. Частный случай этого результата для линейных графов означает, что в любом графе с четным числом ребер можно разбить ребра на пути длины два. Совершенные сопоставления можно использовать для получения другой характеристики графов без клешней: это в точности графы, в которых каждый связный индуцированный подграф четного порядка имеет идеальное сопоставление. [8]

Доказательство Самнера более убедительно показывает, что в любом связном графе без клешней можно найти пару смежных вершин, удаление которых оставляет оставшийся граф связным. Чтобы показать это, Самнер находит пару вершин u и v, которые находятся как можно дальше друг от друга в графе, и выбирает w в качестве соседа вершины v, которая находится как можно дальше от u ; как он показывает, ни v, ни w не могут лежать ни на каком кратчайшем пути от любого другого узла к u , поэтому удаление v и wоставляет оставшийся граф связанным. Повторное удаление совпадающих пар вершин таким образом формирует идеальное соответствие в данном графе без клешней.

Та же идея доказательства верна в более общем случае, если u - любая вершина, v - любая вершина, которая максимально удалена от u , а w - любой сосед v , максимально удаленный от u . Кроме того, удаление v и w из графика не меняет других расстояний от u . Следовательно, процесс формирования сопоставления путем поиска и удаления пар vw , которые максимально удалены от u, может быть выполнен с помощью одного обхода после порядка первого в ширину дерева поиска графа с корнем u, за линейное время. Chrobak, Naor & Novick (1989) предлагают альтернативный алгоритм линейного времени, основанный на поиске в глубину , а также эффективные параллельные алгоритмы для той же проблемы.

Faudree, Flandrin & Ryjáček (1997) перечисляют несколько связанных результатов, в том числе следующие: ( r  - 1) -связные K 1, r -свободные графы четного порядка имеют идеальное сопоставление для любого r  ≥ 2; графы нечетного порядка без клешней с не более чем одной вершиной степени один могут быть разбиты на нечетный цикл и паросочетание; для любого k, которое составляет не более половины минимальной степени графа без клешней, в котором либо k, либо число вершин четно, граф имеет k -фактор; и, если граф без клешней является (2 k  + 1) -связным, то любое k- реберное сопоставление может быть расширено до идеального сопоставления.

Независимые наборы [ править ]

Немаксимальный независимый набор (два фиолетовых узла) и увеличивающийся путь

Независимое множество в линии графике соответствует соответствия в базовой графике, множество ребер никакие два из которых разделяют конечную точку. Алгоритм цветения из Edmonds (1965) находит соответствие максимальной в любом графике в полиномиальное время, что эквивалентно вычисления максимального независимого множества в линейных графиках. Это было независимо расширено до алгоритма для всех графов без когтей Сбихи (1980) и Минти (1980) . [9]

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

Алгоритм Sbihi воссоздает шаг сжатия цветков алгоритма Эдмондса и добавляет аналогичный, но более сложный шаг сжатия клики . Подход Минти состоит в том, чтобы преобразовать экземпляр проблемы во вспомогательный линейный граф и напрямую использовать алгоритм Эдмондса для поиска дополнительных путей. После исправления, сделанного Накамурой и Тамурой 2001 , результат Минти можно также использовать для решения за полиномиальное время более общей проблемы поиска в графах без клешней независимого набора максимального веса. Известны также обобщения этих результатов на более широкие классы графов. [9] Показав новую теорему о структуре , Faenza, Oriolo & Stauffer (2011) дал алгоритм кубического времени, который также работает во взвешенном режиме.

Раскраска, клики и господство [ править ]

Совершенный график представляет собой график , в котором хроматического числа и размера максимальной клики равны, и в котором это равенство сохраняется в каждом индуцированный подграф. Теперь известно ( сильная теорема о совершенном графе ), что совершенные графы можно охарактеризовать как графы, которые не имеют в качестве индуцированных подграфов нечетного цикла или дополнения к нечетному циклу (так называемая нечетная дыра ). [10]Однако в течение многих лет это оставалось нерешенной гипотезой, доказанной только для специальных подклассов графов. Одним из этих подклассов было семейство графов без клешней: несколько авторов обнаружили, что графы без клешней без нечетных циклов и нечетных отверстий идеальны. Совершенные графы без клешней можно распознать за полиномиальное время. В идеальном графе без клешней окрестность любой вершины образует дополнение двудольного графа . Можно раскрасить идеальные графы без клешней или найти в них максимальные клики за полиномиальное время. [11]

Нерешенная задача по математике :

Всегда ли в графах без клешней хроматическое число списка равно их хроматическому числу?

(больше нерешенных задач по математике)

В общем, найти самую большую клику в графе без клешней NP-сложно. [12] Также NP-сложно найти оптимальную раскраску графа, потому что (через линейные графы) эта задача обобщает NP-сложную задачу вычисления хроматического индекса графа. [6] По той же причине NP-сложно найти раскраску, которая обеспечивает коэффициент аппроксимации лучше, чем 4/3. Однако коэффициент аппроксимации, равный двум, может быть достигнут с помощью алгоритма жадной раскраски , потому что хроматическое число графа без клешней больше половины его максимальной степени. Обобщение гипотезы о раскраске списка ребер гласит, что для графов без клешней хроматическое число спискаравно хроматическому числу; эти два числа могут быть далеко друг от друга на других типах графиков. [13]

Графы без клешней являются χ- ограниченными , что означает, что каждый граф без клешней большого хроматического числа содержит большую клику. Более того, из теоремы Рамсея следует, что каждый граф без клешней большой максимальной степени содержит большую клику, размер которой примерно пропорционален квадратному корню из степени. Для связных графов без клешней, которые включают по крайней мере один независимый набор с тремя вершинами, возможна более сильная связь между хроматическим числом и размером клики: в этих графах существует клика размером не менее половины хроматического числа. [14]

Хотя не каждый граф без клешней идеален, графы без клешней обладают еще одним свойством, связанным с совершенством. Граф называется идеальным по доминированию, если он имеет минимальное независимое доминирующее множество и если то же свойство выполняется во всех его индуцированных подграфах. Графы без клешней обладают этим свойством. Чтобы убедиться в этом, пусть D - доминирующее множество в графе без клешней, и предположим, что v и w - две смежные вершины в D ; тогда множество вершин, в которых доминирует v, но не w, должно быть кликой (иначе vбудет центром когтя). Если в каждой вершине этой клики уже доминирует хотя бы один другой член группы D , то v можно удалить, создав меньшее независимое доминирующее множество, а в противном случае v можно заменить одной из недоминируемых вершин в своей клике, создав доминирующее множество с меньше смежностей. Повторяя этот процесс замены, можно в конечном итоге достичь доминирующего множества не больше, чем D , поэтому, в частности, когда начальное множество D является минимальным доминирующим множеством, этот процесс образует столь же малое независимое доминирующее множество. [15]

Несмотря на это свойство идеальности доминирования, NP-сложно определить размер минимального доминирующего множества в графе без клешней. [6] Однако, в отличие от ситуации для более общих классов графов, нахождение минимального доминирующего множества или минимального связного доминирующего множества в графе без когтей является управляемым с фиксированным параметром : его можно решить за время, ограниченное полиномом в размере графика, умноженном на экспоненциальную функцию доминирующего размера множества. [16]

Структура [ править ]

Чудновский и Сеймур (2005) рассматривают серию статей, в которых они доказывают структурную теорию для графов без клешней, аналогичную теореме о структуре графов для семейств минорных замкнутых графов, доказанной Робертсоном и Сеймуром, и теории структур для совершенных графов. что Чудновский, Сеймур и их соавторы использовали для доказательства сильной теоремы о совершенном графе. [10] Теория слишком сложна для подробного описания здесь, но чтобы дать ей представление, достаточно обрисовать два их результата. Во-первых, для специального подкласса графов без клешней, которые они называют квазилинейными графами (эквивалентно локально соподвольными графами), они заявляют, что каждый такой граф имеет одну из двух форм:

  1. Нечеткий круговой интервал график , класс графов представлены геометрический точками и дугами на окружности, обобщающий соответствующие круговые диаграммы дуги.
  2. Граф, построенный из мультиграфа путем замены каждого ребра нечетким линейным интервальным графом . Это обобщает конструкцию линейного графа, в котором каждое ребро мультиграфа заменено вершиной. Нечеткие линейные интервальные графы строятся так же, как нечеткие круговые интервальные графы, но на линии, а не на окружности.

Чудновский и Сеймур классифицируют произвольные связные графы без клешней на один из следующих:

  1. Шесть конкретных подклассов графов без клешней. Три из них - это линейные графы, графы с собственными дугами окружности и индуцированные подграфы икосаэдра; остальные три содержат дополнительные определения.
  2. Графы формируются четырьмя простыми способами из более мелких графов без клешней.
  3. Антипризматические графы , класс плотных графов, определяемых как графы без клешней, в которых каждые четыре вершины индуцируют подграф, по крайней мере, с двумя ребрами.

Большая часть работы по их теории структуры включает дальнейший анализ антипризматических графов. Граф Шлефли , сильно регулярный граф без клешней с параметрами srg (27,16,10,8), играет важную роль в этой части анализа. Эта структурная теория привела к новым достижениям в полиэдральной комбинаторике и новым оценкам хроматического числа графов без клешней, [5] [17], а также к новым алгоритмам с фиксированными параметрами для доминирующих множеств в графах без клешней. [18]

Заметки [ править ]

  1. ^ a b c Faudree, Flandrin & Ryjáček (1997) , стр. 88.
  2. ^ Бейнеке (1968) .
  3. ^ a b Faudree, Flandrin & Ryjáček (1997) , стр. 89.
  4. ↑ Чудновский и Сеймур (2008) .
  5. ^ a b c Чудновский и Сеймур (2005) .
  6. ^ a b c Faudree, Flandrin & Ryjáček (1997) , стр. 132.
  7. ^ Итай & Rodeh (1978) .
  8. ^ a b Faudree, Flandrin & Ryjáček (1997) , стр. 120–124.
  9. ^ a b Faudree, Flandrin & Ryjáček (1997) , стр. 133–134.
  10. ^ а б Чудновский и др. (2006) .
  11. ^ Faudree, Flandrin & Ryjáček (1997) , стр. 135-136.
  12. ^ Faudree, Flandrin & Ryjáček (1997) наблюдать на р. 132, что NP-трудность клик в графах без клешней следует из NP-сложности проблемы независимых множеств в графах без треугольников , NP-трудность доказана Поляком (1974).
  13. ^ Gravier & Maffray (2004) .
  14. ↑ Чудновский и Сеймур (2010) .
  15. ^ Faudree, Flandrin & Ryjáček (1997) , стр. 124-125.
  16. ^ Cygan et al. (2011) ; Hermelin et al. (2011) .
  17. ^ Король и Рид (2015) .
  18. ^ Hermelin et al. (2011) .

Ссылки [ править ]

  • Beineke, LW (1968), "Производные графы орграфов", в Sachs, H .; Voss, H.-J .; Уолтер, Х.-Дж. (ред.), Beiträge zur Graphentheorie , Leipzig: Teubner, pp. 17–33.
  • Хробак, Марек; Наор, Иосиф; Новик, Марк Б. (1989), "Использование остовных деревьев ограниченной степени в разработке эффективных алгоритмов на графах без клешней", в Dehne, F .; Sack, J.-R. ; Санторо, Н. (ред.), Алгоритмы и структуры данных: семинар WADS '89, Оттава, Канада, август 1989 г., Труды , конспекты лекций по вычислительной технике. Sci . , 382 , Берлин:. Springer, С. 147-162, DOI : 10.1007 / 3-540-51542-9_13 , ЛВП : 1813/6891.
  • Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), "Сильная совершенная теорема графа" (PDF) , Анналы математики , 164 (1): 51-229, Arxiv : математика / 0212070 , DOI : 10,4007 / annals.2006.164.51.
  • Чудновский, Мария ; Сеймур, Пол (2005), "Структура графов без клешней" (PDF) , Обзоры по комбинаторике 2005 , London Math. Soc. Lecture Note Ser., 327 , Cambridge: Cambridge Univ. Press, стр. 153–171, MR  2187738.
  • Чудновский, Мария ; Seymour, Пол (2008), ". Лапка свободных графиков III Круговая графы интервалов" (PDF) , Журнал комбинаторной теории , серии B, 98 (4): 812-834, DOI : 10.1016 / j.jctb.2008.03. 001 , Руководство MR  2418774.
  • Чудновский, Мария ; Seymour, Paul (2010), "лапка свободных графиков VI Раскраска.", Журнал комбинаторной теории , серии B, 100 (6): 560-572, DOI : 10.1016 / j.jctb.2010.04.005 , MR  2718677.
  • Циган, Марек; Филип, Дживаргезе; Пилипчук, Марцин; Пилипчук, Михал; Войтащик, Якуб Онуфри (2011), «Доминирующее множество - это фиксированный параметр, управляемый в графах без когтей», Теоретическая информатика , 412 (50): 6982–7000, arXiv : 1011.6239 , doi : 10.1016 / j.tcs.2011.09.010 , Руководство по ремонту  2894366.
  • Эдмондс, Джек (1965), "Пути, деревья и цветы", Canadian Journal математики , 17 (0): 449-467, DOI : 10,4153 / CJM-1965-045-4 , MR  0177907.
  • Фаэнца, Юрий; Ориоло, Джанпаоло; Штауффер, Готье (2011), «Алгоритмическое разложение графов без когтей, ведущее к O (n 3 ) -алгоритму для задачи взвешенного стабильного множества», Труды двадцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (PDF ) , SODA '11, Сан - Франциско, Калифорния:. SIAM, стр 630-646, DOI : 10,1137 / 1.9781611973082.49.
  • Фодри, Ральф ; Фландрин, Эвелин; Ryjáček, Зденек (1997), "лапка свободной графики - опрос А", дискретной математики , 164 (1-3): 87-147, DOI : 10.1016 / S0012-365X (96) 00045-3 , МР  1432221.
  • Гольдберг, Эндрю В .; Карзанов, Александр В. (1996), "Проблемы пути в кососимметричных графах", Combinatorica , 16 (3): 353–382, doi : 10.1007 / BF01261321.
  • Гравье, Сильвен; Maffray, Фредерик (2004), "На выбор количества кулачковых свободных совершенных графов", Дискретная математика , 276 (1-3): 211-218, DOI : 10.1016 / S0012-365X (03) 00292-9 , MR  2046636.
  • Гермелин, Дэнни; Мних, Матиас; ван Леувен, Эрик Ян; Woeginger, Gerhard (2011), «Доминирование, когда звезды не светят», Автоматы, языки и программирование: 38-й международный коллоквиум, ICALP 2011, Цюрих, Швейцария, 4-8 июля 2011 г., Материалы, часть I , Конспекты лекций по информатике , 6755 , Цюрих, Швейцария, стр 462-473,. Arxiv : 1012.0012 , DOI : 10.1007 / 978-3-642-22006-7_39.
  • Итаи, Алон; Rodeh, Майкл (1978), "Нахождение минимальной цепи в графе", SIAM журнал по вычислениям , 7 (4): 413-423, DOI : 10,1137 / 0207033 , МР  0508603.
  • Кинг, Эндрю Д .; Рид, Брюс А. (2015), «Графы без когтей, скелетные графы и более сильная гипотеза о ω, Δ и χ», Journal of Graph Theory , 78 (3): 157–194, arXiv : 1212.3036 , doi : 10.1002 / jgt.21797.
  • Клокс, Тон; Крач, Дитер; Мюллер, Хайко (2000), «Эффективный поиск и подсчет малых индуцированных подграфов», Письма об обработке информации , 74 (3–4): 115–121, DOI : 10.1016 / S0020-0190 (00) 00047-8 , MR  1761552.
  • Лас Вергнас, М. (1975), «Заметка о сопоставлениях в графах», Cahiers du Centre d'Etudes de Recherche Opérationnelle , 17 (2-3-4): 257–260, MR  0412042.
  • Минти, Джордж Дж. (1980), "О максимальных независимых наборах вершин в графах без когтей", Журнал комбинаторной теории, серия B , 28 (3): 284–304, DOI : 10.1016 / 0095-8956 (80) 90074-X , Руководство по ремонту  0579076.
  • Накамура, Дайшин; Тамура, Акихиса (2001), «Пересмотр алгоритма Минти для поиска максимально взвешенного стабильного набора графа без когтей» , Журнал Общества исследования операций Японии , 44 (2): 194–204.
  • Палмер, Эдгар М .; Читайте, Рональд С.; Робинсон, Роберт У. (2002), "Counting коготь свободных кубических графов" (PDF) , SIAM журнал по дискретной математике , 16 (1): 65-73, DOI : 10,1137 / S0895480194274777 , MR  1972075.
  • Поляк, Сватоплюк (1974), «Заметка о стабильных множествах и раскрасках графов», Commentationes Mathematicae Universitatis Carolinae , 15 : 307–309, MR  0351881.
  • Sbihi, Наджиб (1980), "Algorithme научно-исследовательский d'ООН стабильная де cardinalité максимальная йапз ипа Graphe без étoile", дискретная математика , 29 (1): 53-76, DOI : 10.1016 / 0012-365X (90) 90287-R , Руководство по ремонту  0553650.
  • Самнер, Дэвид П. (1974), "Графы с 1-факторов", Труды Американского математического общества , Американского математического общества, 42 (1): 8-12, DOI : 10,2307 / 2039666 , JSTOR  2039666 , MR  0323648.

Внешние ссылки [ править ]

  • Графы без клешней , Информационная система о включениях классов графов
  • Муган, Джонатан Уильям; Вайсштейн, Эрик В. , «График без когтей» , MathWorld