Перекос раздела

Косое разбиение хордального графа . С левой стороны перегородки верхняя и нижняя части отсоединены друг от друга. В правой части разбиения существуют все возможные ребра сверху вниз, образующие граф, дополнение которого несвязно.

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

Определение

Косое разбиение графа $G$ является разбиением своих вершин на два подмножества $X$ и $Y$ для которого индуцированный подграф $G[X]$ несвязен и индуцированный подграф $G[Y]$ является дополнением несвязного графа (конесвязного).Эквивалентно, косое разбиение графа $G$ можно описать разбиением вершин $G$ на четыре подмножества $A$, $B$, $C$, и $D$, такие, что нет ребер из $A$ к $B$ и такой, что все возможные ребра из $C$ к $D$ существовать; для такого разбиения индуцированные подграфы $G[A\cup B]$ и $G[C\cup D]$ несвязны и соразвязны соответственно, поэтому мы можем принять $X=A\cup B$ и $Y=C\cup D$.

Примеры

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

Если граф имеет косое разбиение, то же самое имеет и его дополнение . Например, дополнения к графам путей имеют косые разбиения, а дополнения к графам циклов — нет.

Особые случаи

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

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

Звездчатый разрез на графике $G$ — вершинный разделитель , в котором одна из вершин-разделителей смежна со всеми остальными. Каждый разделитель клик представляет собой звездообразное сечение. Граф со звездчатым разрезом (с более чем одной вершиной) обязательно имеет косое разбиение, в котором конесвязный подграф состоит из вершин звездчатого разреза, а несвязный подграф состоит из всех остальных вершин.

Модуль . (или однородное множество) — это нетривиальное подмножество $H$ вершин $G$ такая, что для каждой вершины $v$ этого нет в $H$, или $v$ смежна со всеми вершинами в $H$ или никому из них. Если график $G$ есть модуль $H$ и вне него существуют обе вершины, смежные со всеми вершинами в $H$ и другие вершины, не примыкающие ни к одной из них, то $G$ имеет звездообразное сечение, состоящее из одной вершины в модуле вместе с ее соседями вне модуля. С другой стороны, если существует модуль, в котором одно из этих двух подмножеств пусто, то граф несвязен или сонесвязен и снова (за тремя простыми исключениями) имеет косое множество.

История

Косые разбиения были введены Хваталом (1985) в связи с совершенными графами . Хватал доказал, что минимально несовершенный граф не может иметь звездчатого разреза. Тривиально, несвязные графы не могут быть минимально несовершенными, а также было известно, что графы с кликовыми разделителями или модулями не могут быть минимально несовершенными. Клод Берже в начале 1960-х предположил, что совершенные графы — это то же самое, что и графы Бержа, графы без индуцированного нечетного цикла (длины пять или более) или его дополнения и (поскольку циклы и их дополнения не имеют косых разбиений) минимальный граф, не являющийся Берджем, может иметь косое разбиение. Вдохновленный этими результатами, Хватал предположил, что ни один минимально несовершенный граф не может иметь косого разбиения. Ряд авторов доказали частные случаи этой гипотезы, но она оставалась нерешенной в течение многих лет.

Косые разбиения приобрели значение, когда их использовали Чудновский и др. (2006) доказать сильную теорему о совершенных графах о том, что графы Бержа действительно такие же, как и идеальные графы. Чудновский и др. не смогли напрямую доказать гипотезу Хватала, но вместо этого доказали более слабый результат, а именно, что минимальный контрпример к теореме (если он существовал) не мог иметь сбалансированного косого разбиения, косого разбиения, в котором каждый индуцированный путь с конечными точками на одной стороне перегородка и внутренние вершины на другой стороне имеют четную длину. Этот результат стал ключевой леммой в их доказательстве, а полная версия леммы Хватала следует из их теоремы.

В теории структурных графов

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

Более простой пример структурной декомпозиции с использованием косых перегородок дан Сеймуром (2006) . Он заметил, что каждый граф сравнимости является полным , двудольным или имеет косое разбиение. Ведь если каждый элемент частично упорядоченного множества является либо минимальным элементом , либо максимальным элементом, то соответствующий граф сравнимости является двудольным. Если упорядочение является полным порядком , то соответствующий граф сравнимости является полным. Если ни один из этих двух случаев не возникает, но каждый элемент, не являющийся ни минимальным, ни максимальным, сравним со всеми другими элементами, то либо разбиение на минимальный и неминимальный элементы (если минимальных элементов более одного), либо разбиение на максимальный и немаксимальный элементы (если максимальных элементов более одного) образуют звездообразное сечение. А в оставшемся случае существует элемент $x$ частичного порядка, который не является минимальным, не максимальным и не сравнимым со всеми другими элементами; в этом случае имеется косое разбиение (дополнение к звездообразному разрезу), в котором сонесвязная сторона состоит из элементов, сравнимых с $x$ (не включая $x$ сам), а отключенная сторона состоит из остальных элементов.

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

Алгоритмы и сложность

Косое разбиение данного графа, если оно существует, может быть найдено за полиномиальное время . Первоначально это было показано де Фигейредо и др. (2000) , но с непрактично большим временем работы $O(n^{101})$, где $n$ — количество вершин во входном графе. Кеннеди и Рид (2008) улучшили время работы до $O(n^{4}m)$; здесь $m$ количество входных ребер.

является NP-полной проверка наличия в графе косого разбиения, в котором одна из частей сонесвязной стороны независима. Проверка того, содержит ли данный граф сбалансированное косое разбиение, также является NP-полной для произвольных графов, но может быть решена за полиномиальное время в идеальных графах.

Ссылки

• Чудновская Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе» , Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , doi : 10.4007/annals.2006.164.51 .
• Хватал, В. (1985), «Звездные разрезы и совершенные графы», Журнал комбинаторной теории , серия B, 39 (3): 189–199, doi : 10.1016/0095-8956(85)90049-8 , MR   0815391 .
• Корнюжоль, Г. ; Рид, Б. (1993), «Полные многочастные разрезы в минимальных несовершенных графах», Журнал комбинаторной теории , серия B, 59 (2): 191–198, doi : 10.1006/jctb.1993.1065 , MR   1244930 .
• Дантас, Симона; де Фигейредо, Селина М.Х.; Кляйн, Суламита; Гравье, Сильвен; Рид, Брюс А. (2004), «Проблема стабильного перекоса разделения», Discrete Applied Mathematics , 143 (1–3): 17–22, doi : 10.1016/j.dam.2004.01.001 , MR   2087864 .
• де Фигейредо, Селина М.Х.; Кляйн, Суламита; Кохаякава, Ёсихару ; Рид, Брюс А. (2000), «Эффективный поиск косых разделов», Journal of Algorithms , 37 (2): 505–521, doi : 10.1006/jagm.1999.1122 , MR   1788847 .
• Хейворд, Райан Б. (1985), «Слабо триангулированные графы», Журнал комбинаторной теории , серия B, 39 (3): 200–208, doi : 10.1016/0095-8956(85)90050-4 , MR   0815392 .
• Кеннеди, Уильям С.; Рид, Брюс (2008), «Быстрое распознавание перекоса», Вычислительная геометрия и теория графов: Международная конференция, KyotoCGGT 2007, Киото, Япония, 11–15 июня 2007 г., Пересмотренные избранные статьи , Конспекты лекций по информатике , том. 4535, Берлин: Springer, стр. 101–107, doi : 10.1007/978-3-540-89550-3_11 , MR   2672388 .
• Ловас, Ласло (1972), «Нормальные гиперграфы и гипотеза об идеальном графе», Discrete Mathematics , 2 (3): 253–267, doi : 10.1016/0012-365X(72)90006-4 .
• Рид, Брюс (2008), «Скошенные разбиения в идеальных графах» (PDF) , Discrete Applied Mathematics , 156 (7): 1150–1156, doi : 10.1016/j.dam.2007.05.054 , MR   2404228 .
• Руссель, Ф.; Рубио, П. (2001), «О косых разбиениях в минимальных несовершенных графах», Журнал комбинаторной теории , серия B, 83 (2): 171–190, doi : 10.1006/jctb.2001.2044 , MR   1866394 .
• Сеймур, Пол (2006), «Как было найдено доказательство сильной гипотезы о совершенном графе» (PDF) , Gazette des Mathématiciens (109): 69–83, MR   2245898 .
• Тротиньон, Николя (2008), «Разложение графов Бержа и обнаружение сбалансированных косых разбиений» (PDF) , Journal of Combinatorial Theory , Series B, 98 (1): 173–225, arXiv : 1309.0680 , doi : 10.1016/j.jctb. 2007.07.004 , МР   2368032 .