Перекос раздела - Skew partition

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

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

Определение

Косое разбиение графа ${ 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]

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

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

История

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

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

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

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

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

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

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

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

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

Примечания

^ ^а ^б ^c ^d Рид (2008).
^ Рид (2008). Отсутствие модулей в минимально несовершенных графах использовалось Ловас (1972) в его доказательстве слабая теорема о совершенном графе.
^ Видеть Корнежоль и Рид (1993) для случая, когда совместно отключенная сторона раздела является многочастной, и Руссель и Рубио (2001) для случая, когда одна из двух частей совместно отсоединенной стороны является независимой.
^ Сеймур (2006).
^ Дантас и др. (2004).
^ Тротиньон (2008).