График без когтей - Claw-free graph

Коготь

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

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

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

Примеры

Правильный икосаэдр, многогранник, вершины и ребра которого образуют граф без клешней.
  • Линейный график 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 должны совместно использовать одну из этих конечных точек друг с другом. Линейные графы можно охарактеризовать с помощью девяти запрещенных подграфов; коготь - самый простой из этих девяти графов. Эта характеристика послужила первоначальной мотивацией для изучения графов без клешней.
  • В графах де Брейно (графы, вершины представляют собой п -битового двоичных строк для некоторого п , а ребра представляют собой ( п  - 1) -битовым перекрываются между двумя строками) являются зубчатыми бесплатно. Один из способов показать это - построить граф де Брейна для n- битных строк как линейный граф графа де Брейна для ( n  - 1) -битных строк.
  • Дополнение любого треугольника свободного графика является когтем бесплатно. Эти графы включают как частный случай любой полный граф .
  • Правильные интервальные графы , интервальные графы, сформированные как графы пересечений семейств интервалов, в которых ни один интервал не содержит другого интервала, не имеют клешней, потому что четыре правильно пересекающихся интервала не могут пересекаться по образцу клешни. То же самое в более общем случае справедливо для правильных графов дуги окружности .
  • Moser шпиндель , семь вершин графа используется , чтобы обеспечить нижнюю границу для хроматического числа плоскости , является зубчатыми свободным.
  • Графики нескольких многогранников и многогранников являются зубчатыми свободным, в том числе графика тетраэдра и в более общем плане любого симплекса (полный граф), в графу октаэдра и в более общем плане любого поперечного многогранника ( изоморфно к коктейль графу , образованному путем удаления идеального совпадения из полного графа), графа правильного икосаэдра и графа из 16 клеток .
  • Граф Шлефли , сильно регулярный граф с 27 вершинами, не имеет клешней.

Признание

Несложно проверить, что данный граф с n вершинами и m ребрами свободен от когтей за время O ( n 4 ), проверяя каждый набор из 4 вершин, чтобы определить, порождают ли они когти. С большей эффективностью и большей сложностью можно проверить, свободен ли граф от когтей, проверив для каждой вершины графа, что дополнительный граф его соседей не содержит треугольника. Граф содержит треугольник тогда и только тогда, когда куб его матрицы смежности содержит ненулевой диагональный элемент, поэтому поиск треугольника может быть выполнен за ту же асимптотическую границу времени, что и умножение матрицы n  ×  n . Следовательно, при использовании алгоритма Копперсмита – Винограда общее время для этого алгоритма распознавания без когтей будет 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) доказали, что любой связный граф без когтей с четным числом вершин имеет идеальное соответствие . То есть существует такой набор ребер в графе, что каждая вершина является конечной точкой ровно одного из совпадающих ребер. Частный случай этого результата для линейных графов означает, что в любом графе с четным числом ребер можно разбить ребра на пути длины два. Совершенные сопоставления можно использовать для получения другой характеристики графов без клешней: это в точности графы, в которых каждый связный индуцированный подграф четного порядка имеет идеальное сопоставление.

Доказательство Самнера более убедительно показывает, что в любом связном графе без клешней можно найти пару смежных вершин, удаление которых оставляет оставшийся граф связным. Чтобы показать это, Самнер находит пару вершин 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) .

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

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

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

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

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

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

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

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

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

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

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

Состав

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

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

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

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

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

Примечания

использованная литература

внешние ссылки