Косая перегородка

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

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

Определение

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

Примеры

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

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

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

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

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

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

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

История

Косые разбиения были введены Хваталом (1985) в связи с совершенными графами . Хватал доказал, что минимально несовершенный граф не может иметь звездное разрезание. Тривиально, несвязные графы не могут быть минимально несовершенными, и было также известно, что графы с разделителями клик или модулями не могут быть минимально несовершенными. ^[2] Клод Берже предположил в начале 1960-х годов, что совершенные графы - это то же самое, что и графы Берже, графы без индуцированного нечетного цикла (длиной пять или более) или его дополнения, и (поскольку циклы и их дополнения не имеют косых разбиений) никакой минимальный не-Берже граф не может иметь косого разбиения. Мотивированный этими результатами, Хватал предположил, что никакой минимально несовершенный граф не может иметь косого разбиения. Несколько авторов доказали особые случаи этой гипотезы, но она оставалась нерешенной в течение многих лет. ^[3]

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

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

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

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

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

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

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

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

Примечания

1. Рид (2008).
2. Рид (2008). Несуществование модулей в минимально несовершенных графах было использовано Ловасом (1972) в его доказательстве слабой теоремы о совершенном графе .
3. См. Cornuéjols & Reed (1993) для случая, когда соразъединенная сторона перегородки является многодольной, и Roussel & Rubio (2001) для случая, когда одна из двух частей соразъединенной стороны является независимой.
4. Сеймур (2006).
5. Дантас и др. (2004).
6. Тротиньон (2008).

Ссылки

• Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе», Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , doi :10.4007/annals.2006.164.51.
• Chvátal, V. (1985), «Звездные сечения и совершенные графы», Журнал комбинаторной теории , Серия B, 39 (3): 189–199, doi :10.1016/0095-8956(85)90049-8, MR  0815391.
• Cornuéjols, G. ; Reed, B. (1993), "Полные многодольные разрезы в минимальных несовершенных графах", Журнал комбинаторной теории , Серия B, 59 (2): 191–198, doi : 10.1006/jctb.1993.1065 , MR  1244930.
• Dantas, Simone; de ​​Figueiredo, Celina MH; Klein, Sulamita; Gravier, Sylvain; Reed, Bruce A. (2004), "Проблема стабильного косого разбиения", Discrete Applied Mathematics , 143 (1–3): 17–22, doi : 10.1016/j.dam.2004.01.001 , MR  2087864.
• de Figueiredo, Celina MH; Klein, Sulamita; Kohayakawa, Yoshiharu ; Reed, Bruce A. (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), "Быстрое распознавание косых разбиений", Computational Geometry and Graph Theory: Международная конференция, KyotoCGGT 2007, Киото, Япония, 11–15 июня 2007 г., Revised Selected Papers , Lecture Notes in Computer Science , т. 4535, Берлин: Springer, стр. 101–107, doi :10.1007/978-3-540-89550-3_11, MR  2672388.
• Ловас, Ласло (1972), «Нормальные гиперграфы и гипотеза о совершенном графе», Дискретная математика , 2 (3): 253–267, doi :10.1016/0012-365X(72)90006-4.
• Рид, Брюс (2008), «Косые разбиения в совершенных графах» (PDF) , Дискретная прикладная математика , 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) , Журнал комбинаторной теории , Серия B, 98 (1): 173–225, arXiv : 1309.0680 , doi : 10.1016/j.jctb.2007.07.004, MR  2368032.