График без когтей

коготь

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

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

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

Примеры

Правильный икосаэдр — многогранник, вершины и ребра которого образуют граф без когтей.

• Линейный граф L ( G ) любого графа G не имеет клешней; L ( G ) имеет вершину для каждого ребра G , и вершины смежны в L ( G если соответствующие ребра имеют общую конечную точку в G. ) , Линейный граф L ( G содержать клешню, потому что если три ребра , _e2 , и _{) не} e3 в _общие G имеют конечные точки с другим ребром , _то по принципу ячейки по крайней мере два из e1 _e4 , e2 _e1 может и e ₃ должны совместно использовать одну из этих конечных точек. Линейные графы можно охарактеризовать с помощью девяти запрещенных подграфов; коготь — самый простой из этих девяти графов. Эта характеристика послужила первоначальной мотивацией для изучения графов без когтей.
• Дополнение любого графа без треугольников не имеет клешней. Эти графы включают в себя в качестве частного случая любой полный граф .
• Правильные графы интервалов , графы интервалов, сформированные как графы пересечений семейств интервалов, в которых ни один интервал не содержит другой интервал, не содержат когтей, поскольку четыре правильно пересекающихся интервала не могут пересекаться по образцу когтя. То же самое верно и в более общем плане для правильных графов с дугами окружности .
• Веретено Мозера , семивершинный граф, используемый для определения нижней границы хроматического числа плоскости , не имеет когтей.
• Графы нескольких многогранников и многогранников не имеют когтей, включая граф тетраэдра и , в более общем смысле, любого симплекса (полный граф), граф октаэдра и, в более общем плане, любого перекрестного многогранника ( изоморфного графу коктейльной вечеринки , сформированному удалением совершенного паросочетания из полного графа), график правильного икосаэдра , и график 16-клеточного .
• Граф Шлефли — сильно регулярный граф с 27 вершинами — не имеет когтей.

Признание

Несложно проверить, что данный граф с n вершинами и m ребрами не имеет клешней за время O( n ⁴ ), проверяя каждую четверку вершин, чтобы определить, вызывают ли они коготь. С большей эффективностью и большей сложностью можно проверить, свободен ли граф от когтей, проверив для каждой вершины графа, что граф дополнения ее соседей не содержит треугольника. Граф содержит треугольник тогда и только тогда, когда куб его матрицы смежности содержит ненулевой диагональный элемент, поэтому поиск треугольника может быть выполнен за то же асимптотическое время, что и n × n умножение матрицы . Следовательно, при использовании алгоритма Копперсмита-Винограда общее время для этого алгоритма распознавания без когтей будет равно O( n ^3.376 ).

Клокс, Крач и Мюллер (2000) отмечают, что в любом графе без когтей каждая вершина имеет не более 2 √ m соседей; в противном случае по теореме Турана у соседей вершины не было бы достаточного количества оставшихся ребер, чтобы сформировать дополнение графа без треугольников. Это наблюдение позволяет выполнять проверку каждой окрестности в описанном выше алгоритме, основанном на быстром умножении матриц, за то же асимптотическое время, что и при умножении матриц 2 √ m × 2 √ m , или быстрее для вершин с еще более низкими степенями. Наихудший случай для этого алгоритма возникает, когда каждая вершина Ω( √ m ) имеет соседей Ω( √ m ), а остальные вершины имеют мало соседей, поэтому общее время составляет O( m ^3.376/2 ) = O( м ^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 за линейное время. Хробак, Наор и Новик (1989) предлагают альтернативный алгоритм линейного времени, основанный на поиске в глубину , а также эффективные параллельные алгоритмы для той же задачи.

Фаудри, Фландрин и Рыячек (1997) перечисляют несколько связанных результатов, в том числе следующие: ( r − 1)-связные K _{1, r} -свободные графы четного порядка имеют идеальные паросочетания для любого r ≥ 2; графы без когтей нечетного порядка с не более чем одной вершиной степени один можно разбить на нечетный цикл и паросочетание; для любого k, составляющего не более половины минимальной степени графа без когтей, в котором либо k , либо число вершин четно, граф имеет k -фактор; и если граф без клешней (2 k + 1)-связен, то любое паросочетание k -ребер можно расширить до идеального паросочетания.

Независимые наборы

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

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

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

Алгоритм Сбихи воссоздает этап сжатия цветка алгоритма Эдмондса и добавляет аналогичный, но более сложный этап сжатия клики . Подход Минти состоит в том, чтобы преобразовать экземпляр задачи во вспомогательный линейный граф и напрямую использовать алгоритм Эдмондса для поиска дополнительных путей. После поправки Накамуры и Тамуры (2001) результат Минти также можно использовать для решения за полиномиальное время более общей проблемы поиска в графах без когтей независимого набора максимального веса. Известны также обобщения этих результатов на более широкие классы графов. Показывая новую структурную теорему , Фаэнца, Ориоло и Штауффер (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) — играет важную роль в этой части анализа. Эта теория структуры привела к новым достижениям в многогранной комбинаторике и новым оценкам хроматического числа графов без когтей. а также к новым алгоритмам с фиксированными параметрами для доминирования множеств в графах без когтей.

Ссылки

• Бейнеке, Л.В. (1968), «Производные графы орграфов», в Саксе, Х.; Восс, Х.-Дж.; Вальтер, Х.-Дж. (ред.), «Вклад в теорию графов» , Лейпциг: Тойбнер, стр. 17–33 .
• Хробак, Марек; Наор, Джозеф; Новик, Марк Б. (1989), «Использование остовных деревьев ограниченной степени при разработке эффективных алгоритмов на графах без когтей», в Дене, Ф.; Сак, Ж.-Р. ; Санторо, Н. (ред.), Алгоритмы и структуры данных: Семинар WADS '89, Оттава, Канада, август 1989 г., Материалы , конспекты лекций по вычислительной технике. наук, том. 382, Берлин: Springer, стр. 147–162, doi : 10.1007/3-540-51542-9_13 , hdl : 1813/6891 , ISBN  978-3-540-51542-5 .
• Чудновская Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе» (PDF) , Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , doi : 10.4007/annals.2006.164.51 , S2CID   119151552 .
• Чудновская Мария ; Сеймур, Пол (2005), «Структура графов без когтей» (PDF) , Обзоры по комбинаторике 2005 г. , London Math. Соц. Лекционная конспект. Сер., т. 1, с. 327, Кембридж: Кембриджский университет. Пресс, стр. 153–171, МР   2187738 .
• Чудновская Мария ; Сеймур, Пол (2008), «Графы без когтей. III. Графы круговых интервалов» (PDF) , Журнал комбинаторной теории , серия B, 98 (4): 812–834, doi : 10.1016/j.jctb.2008.03. 001 , МР   2418774 .
• Чудновская Мария ; Сеймур, Пол (2010), «Графы без когтей VI. Раскраска», Журнал комбинаторной теории , серия B, 100 (6): 560–572, CiteSeerX   10.1.1.220.7715 , doi : 10.1016/j.jctb.2010.04 .005 , МР   2718677 .
• Циган, Марек; Филип, Гиваргезе; Пилипчук, Марцин; Пилипчук, Михал; Войтащик, Якуб Онуфрий (2011), «Доминирующий набор - это фиксированный параметр, который можно отслеживать в графах без когтей», Theoretical Computer Science , 412 (50): 6982–7000, arXiv : 1011.6239 , doi : 10.1016/j.tcs.2011.09.010 , МР   2894366 , S2CID   16339210 .
• Эдмондс, Джек (1965), «Пути, деревья и цветы», Canadian Journal of Mathematics , 17 : 449–467, doi : 10.4153/CJM-1965-045-4 , MR   0177907 , S2CID   18909734 .
• Фаэнца, Юрий; Ориоло, Джанпаоло; Штауффер, Готье (2011), «Алгоритмическая декомпозиция графов без клешней, ведущая к O (n ³ )-алгоритм для проблемы взвешенного устойчивого множества», Труды двадцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (PDF) , SODA '11, Сан-Франциско, Калифорния: SIAM, стр. 630–646, doi : 10.1137/ 1.9781611973082.49 , ISBN  978-0-89871-993-2 , S2CID   13353335 .
• Фаудри, Ральф ; Фландрин, Эвелин; Рыячек, Зденек (1997), «Графы без клешней — обзор», Discrete Mathematics , 164 (1–3): 87–147, doi : 10.1016/S0012-365X(96)00045-3 , MR   1432221 .
• Гольдберг, Эндрю В .; Карзанов, Александр В. (1996), «Задачи о путях в кососимметричных графах», Combinatorica , 16 (3): 353–382, doi : 10.1007/BF01261321 , S2CID   16308467 .
• Гравье, Сильвен; Маффрэ, Фредерик (2004), «О выборе числа идеальных графов без клешней», Discrete Mathematics , 276 (1–3): 211–218, doi : 10.1016/S0012-365X(03)00292-9 , MR   2046636 .
• Гермелин, Дэнни; Мних, Матиас; ван Леувен, Эрик Ян; Воегингер, Герхард (2011), «Доминирование при беззвездном свете», Автоматы, языки и программирование: 38-й международный коллоквиум, ICALP 2011, Цюрих, Швейцария, 4–8 июля 2011 г., Материалы, Часть I , Конспекты лекций по информатике , том. 6755, Цюрих, Швейцария, стр. 462–473, arXiv : 1012.0012 , doi : 10.1007/978-3-642-22006-7_39 , ISBN.  978-3-642-22005-0 , S2CID   3080073 {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) .
• Итай, Алон; Роде, Майкл (1978), «Нахождение минимальной схемы в графе», SIAM Journal on Computing , 7 (4): 413–423, doi : 10.1137/0207033 , MR   0508603 .
• Кинг, Эндрю Д.; Рид, Брюс А. (2015), «Графы без когтей, скелетные графы и более сильная гипотеза о ω, Δ и χ», Journal of Graph Theory , 78 (3): 157–194, arXiv : 1212.3036 , doi : 10.1002/jgt.21797 , S2CID   7385598 .
• Клокс, Тон; Крач, Дитер; Мюллер, Хайко (2000), «Эффективный поиск и подсчет небольших индуцированных подграфов», Information Processing Letters , 74 (3–4): 115–121, doi : 10.1016/S0020-0190(00)00047-8 , MR   1761552 .
• Лас Верньяс, М. (1975), «Заметки о сопоставлениях в графах», Cahiers du Center 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-Х , МР   0579076 .
• Накамура, Дайсин; Тамура, Акихиса (2001), «Пересмотр алгоритма Минти для поиска максимально взвешенного стабильного набора графа без когтей» , Журнал Общества исследования операций Японии , 44 (2): 194–204, doi : 10.15807/ jorsj.44.194 .
• Палмер, Эдгар М.; Прочтите, Рональд К.; Робинсон, Роберт В. (2002), «Подсчет кубических графов без когтей» (PDF) , SIAM Journal on Discrete Mathematics , 16 (1): 65–73, doi : 10.1137/S0895480194274777 , MR   1972075 .
• Поляк, Святополк (1974), «Заметки об устойчивых множествах и раскрасках графов», Математические заметки Университета Каролины , 15 : 307–309, MR   0351881 .
• Сбихи, Наджиба (1980), «Алгоритм поиска конюшни максимальной мощности в беззвездном графе», Discrete Mathematics , 29 (1): 53–76, doi : 10.1016/0012-365X(90)90287-R , MR   0553650 .
• Самнер, Дэвид П. (1974), «Графики с 1-факторами», Труды Американского математического общества , 42 (1), Американское математическое общество: 8–12, doi : 10.2307/2039666 , JSTOR   2039666 , MR   0323648 .

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

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