В теории графов , области математики, граф без клешней — это граф, у которого нет клешни в качестве индуцированного подграфа .
Коготь — это другое название полного двудольного графа K 1,3 (т. е. звездного графа , состоящего из трех ребер, трех листьев и центральной вершины). Граф без клешней — это граф, в котором ни один индуцированный подграф не является клешней; т. е. любое подмножество из четырех вершин имеет не только три ребра, соединяющие их в этом шаблоне. Эквивалентно, граф без когтей — это граф, в котором окрестность любой вершины является дополнением графа без треугольников .
Графы без клешней изначально изучались как обобщение линейных графов и получили дополнительную мотивацию благодаря трем ключевым открытиям о них: тот факт, что все связные графы без клешней четного порядка имеют идеальные паросочетания , открытие алгоритмов с полиномиальным временем для поиска максимального независимые множества в графах без клешней и характеристика совершенных графов без клешней . [1] Они являются предметом сотен математических исследовательских работ и нескольких обзоров. [1]
Несложно проверить, что данный граф с n вершинами и m ребрами не содержит клешней за время O( n 4 ), проверяя каждую четверку вершин, чтобы определить, вызывают ли они клешню. [6] С большей эффективностью и большей сложностью можно проверить, свободен ли граф от когтей, проверив для каждой вершины графа, что граф дополнения к ее соседям не содержит треугольника. Граф содержит треугольник тогда и только тогда, когда куб его матрицы смежности содержит ненулевой диагональный элемент, поэтому поиск треугольника может быть выполнен за то же асимптотическое время, что и умножение матрицы n × n . [7] Следовательно, при использовании алгоритма Копперсмита-Винограда общее время для этого алгоритма распознавания без когтей составит O( n 3,376 ).
Клокс, Крач и Мюллер (2000) отмечают, что в любом графе без когтей каждая вершина имеет не более 2 √ m соседей; в противном случае по теореме Турана у соседей вершины не было бы достаточного количества оставшихся ребер, чтобы сформировать дополнение графа без треугольников. Это наблюдение позволяет выполнять проверку каждой окрестности в описанном выше алгоритме, основанном на быстром умножении матриц, за то же асимптотическое время, что и при умножении матриц 2 √ m × 2 √ m , или быстрее для вершин с еще более низкими степенями. Наихудший случай для этого алгоритма возникает, когда каждая из вершин Ω( √ m ) имеет соседей Ω( √ m ), а остальные вершины имеют мало соседей, поэтому общее время составляет O( m 3,376/2 ) = O ( m 1,688 ).
Поскольку графы без когтей включают дополнения к графам без треугольников, количество графов без когтей на n вершинах растет по крайней мере так же быстро, как и количество графов без треугольников, экспоненциально в квадрате n . Число связных графов без когтей на n узлах для n = 1, 2,... равно
Если графам разрешено быть несвязными, число графов будет еще больше: они
Метод Палмера, Рида и Робинсона (2002) позволяет очень эффективно подсчитывать количество кубических графов без когтей, что необычно для задач перечисления графов .
Самнер (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 за линейное время. Хробак, Наор и Новик (1989) предлагают альтернативный алгоритм линейного времени, основанный на поиске в глубину , а также эффективные параллельные алгоритмы для той же задачи.
Фаудри, Фландрин и Риячек (1997) перечисляют несколько связанных результатов, в том числе следующие: ( r − 1)-связные K 1, r -свободные графы четного порядка имеют идеальные паросочетания для любого r ≥ 2; графы без когтей нечетного порядка с не более чем одной вершиной степени один можно разбить на нечетный цикл и паросочетание; для любого k , составляющего не более половины минимальной степени графа без когтей, в котором либо k , либо число вершин четно, граф имеет k -фактор; и если граф без клешней (2 k + 1)-связен, то любое паросочетание k -ребер можно расширить до идеального паросочетания.
Независимый набор в линейном графе соответствует паросочетанию в лежащем в его основе графе, множестве ребер, никакие два из которых не имеют общей конечной точки. Алгоритм Блума Эдмондса (1965) находит максимальное паросочетание в любом графе за полиномиальное время, что эквивалентно вычислению максимального независимого множества в линейных графах. Это было независимо расширено Сбихи (1980) и Минти (1980) до алгоритма для всех графов без когтей. [9]
Оба подхода используют наблюдение, что в графах без когтей ни одна вершина не может иметь более двух соседей в независимом наборе, и поэтому симметричная разница двух независимых наборов должна индуцировать подграф степени не выше двух; то есть это объединение путей и циклов. В частности, если I — немаксимальное независимое множество, оно отличается от любого максимального независимого множества четными циклами и так называемыми увеличивающими путями : индуцированными путями , которые чередуются между вершинами не из I и вершинами из I и для которых обе конечные точки имеют только один сосед во мне . Поскольку симметричная разность I с любым увеличивающим путем дает большее независимое множество, задача, таким образом, сводится к поиску увеличивающих путей до тех пор, пока больше не будет найдено, аналогично тому, как в алгоритмах поиска максимальных паросочетаний.
Алгоритм Сбихи воссоздает этап сжатия цветка алгоритма Эдмондса и добавляет аналогичный, но более сложный этап сжатия клики . Подход Минти состоит в том, чтобы преобразовать экземпляр задачи во вспомогательный линейный граф и напрямую использовать алгоритм Эдмондса для поиска дополнительных путей. После исправления Накамуры и Тамуры, 2001, результат Минти также может быть использован для решения за полиномиальное время более общей проблемы поиска в графах без когтей независимого набора максимального веса. Известны также обобщения этих результатов на более широкие классы графов. [9] Показывая новую структурную теорему, Фаенца, Ориоло и Штауффер (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] Теория слишком сложна, чтобы подробно описывать ее здесь, но чтобы дать представление о ней, достаточно обрисовать два ее результата. Во-первых, для специального подкласса графов без клешней, который они называют квазилинейными графами (т. е. локально кодвудольными графами), они утверждают, что каждый такой граф имеет одну из двух форм:
Чудновский и Сеймур классифицируют произвольные связные графы без клешней к одному из следующих:
Большая часть работы по их теории структуры включает дальнейший анализ антипризматических графов. Граф Шлефли — сильно регулярный граф без клешней с параметрами srg(27,16,10,8) — играет важную роль в этой части анализа. Эта теория структуры привела к новым достижениям в полиэдральной комбинаторике и новым оценкам хроматического числа графов без клешней, [5] [17] , а также к новым управляемым алгоритмам с фиксированными параметрами для доминирования множеств в графах без клешней. [18]
{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ).