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

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

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

Определение [ править ]

Перекос разбиение графа является разбиение его вершин на два подмножества , и для которых индуцированный подграф отсоединен и индуцированный подграф является дополнением отключенного графа (совместно отключен). Эквивалентно, косое разбиение графа может быть описано с помощью разбиения вершин на четыре подмножества , , , и , таким образом, что нет ребра от до и таким образом, что все возможных ребер от до существует; для такого разбиения индуцированные подграфы и разъединены и совместно разъединены соответственно, поэтому мы можем взять и . ${\ 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 \ чашка B]}$ ${\ Displaystyle G [C \ чашка D]}$ ${\ displaystyle X = A \ чашка B}$ ${\ Displaystyle Y = C \ чашка D}$

Примеры [ править ]

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

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

Особые случаи [ править ]

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

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

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

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

История [ править ]

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

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

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

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

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

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

Алгоритмы и сложность [ править ]

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

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

Заметки [ править ]

^ а б в г Рид (2008) .
^ Рид (2008) . Отсутствие модулей в минимально несовершенных графах было использовано Ловасом (1972) в его доказательстве слабой теоремы о совершенном графе .
^ См. Cornuéjols и Reed (1993) для случая, когда совместно отключенная сторона перегородки является многочастной, и Roussel & Rubio (2001) для случая, когда одна из двух частей совместно отключенной стороны является независимой.
^ Сеймур (2006) .
^ Дантас и др. (2004) .
^ Trotignon (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 .; Рид, В. (1993), "Полные мульти-дольные сечения в минимальных графах несовершенных", Журнал комбинаторной теории , Series B, 59 (2): 191-198, DOI : 10,1006 / jctb.1993.1065 , МР 1244930.
Дантас, Симона; де Фигейредо, Селина М.Х.; Кляйн, Суламита; Гравье, Сильвен; Рид, Брюс А. (2004), "Стабильная проблема перекоса раздела", Discrete Applied Mathematics , 143 (1-3): 17-22, DOI : 10.1016 / j.dam.2004.01.001 , MR 2087864.
де Фигейредо, Селина М.Х.; Кляйн, Суламита; Кохаякава, Ёсихару ; Рид, Брюс А. (2000), "Finding косых перегородки эффективно", журнал алгоритмов , 37 (2): 505-521, DOI : 10,1006 / jagm.1999.1122 , MR 1788847.
Hayward, Райан Б. (1985), "Слабосвязанные триангулирован графы", Журнал комбинаторной теории , серии B, 39 (3): 200-208, DOI : 10,1016 / 0095-8956 (85) 90050-4 , MR 0815392.
Кеннеди, Уильям С .; Рид, Брюс (2008), «Быстрое распознавание перекосов», Вычислительная геометрия и теория графов: Международная конференция, KyotoCGGT 2007, Киото, Япония, 11–15 июня 2007 г., Revised Selected Papers , Lecture Notes in Computer Science , 4535 , Berlin :. Спрингер, С. 101-107, DOI : 10.1007 / 978-3-540-89550-3_11 , МР 2672388.
Ловас, Ласло (1972), «Нормальные гиперграфы и гипотеза идеального графа», Дискретная математика , 2 (3): 253–267, DOI : 10.1016 / 0012-365X (72) 90006-4 CS1 maint: discouraged parameter (link).
Рид, Брюс (2008), "косые перегородки в совершенных графах" (PDF) , Discrete Applied Mathematics , 156 (7): 1150-1156, DOI : 10.1016 / j.dam.2007.05.054 , MR 2404228 CS1 maint: discouraged parameter (link).
Руссель, Ф .; Рубио, P. (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.
Trotignon, Николя (2008), "Разложение Berge графики и обнаружения сбалансирован косые разделов" (PDF) , Журнал комбинаторной теории , Series B, 98 (1): 173-225, DOI : 10.1016 / j.jctb.2007.07.004 , Руководство по ремонту 2368032.

[r08-1] а б в г Рид (2008) .

[2] Рид (2008) . Отсутствие модулей в минимально несовершенных графах было использовано Ловасом (1972) в его доказательстве слабой теоремы о совершенном графе .

[3] См. Cornuéjols и Reed (1993) для случая, когда совместно отключенная сторона перегородки является многочастной, и Roussel & Rubio (2001) для случая, когда одна из двух частей совместно отключенной стороны является независимой.

[4] Сеймур (2006) .

[5] Дантас и др. (2004) .

[6] Trotignon (2008) .

[1]