Разделить график - Split graph

Расщепленный граф, разбитый на клику и независимое множество.

В теория графов, раздел математики, разделенный график - граф, вершины которого можно разбить на клика и независимый набор. Сплит-графы впервые были изучены Фёльдесом и Молоток (1977a, 1977b ) и независимо введены Тышкевич и Черняк (1979 ).^[1]

Расщепленный граф может иметь более одного разбиения на клику и независимое множество; например, путь а–б–c представляет собой расщепляемый граф, вершины которого можно разбить тремя различными способами:

the clique {а,б} и независимое множество {c}
the clique {б,c} и независимый набор {а}
the clique {б} и независимое множество {а,c}

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

Связь с другими семействами графов

Из определения ясно, что расщепленные графы замкнуты относительно дополнение.^[3] Другая характеристика расщепленных графов включает дополнение: они хордовые графы то дополняет из них также хордовые.^[4] Так же, как хордовые графы графы пересечений поддеревьев деревьев, расщепленные графы - это графы пересечений различных подсистем звездные графики.^[5] Почти все хордовые графы - это расщепленные графы; то есть в пределе при п уходит в бесконечность, доля п-вершинный хордовый граф, который расщепляется, приближается к одному.^[6]

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

Если граф одновременно является разбитым графом и интервальный график, то его дополнение является как разбитым графом, так и график сопоставимости, наоборот. Графы сравнимости с разбиением, а следовательно, и графы с разбиением интервалов, можно охарактеризовать с помощью набора из трех запрещенных индуцированных подграфов.^[7] Раскол кографы точно графики пороговых значений. Раскол графы перестановок являются в точности интервальными графами, которые имеют дополнения к интервальным графам;^[8]это графы перестановок перестановки с перекосом.^[9] Разделенные графы имеют кохроматическое число 2.

Алгоритмические проблемы

Позволять грамм быть расщепленным графом, разбитым на клику C и независимый набор я. Затем каждые максимальная клика в расщепленном графе либо C сам, или район вершины в я. Таким образом, легко идентифицировать максимальную клику и дополнительно максимальный независимый набор в разделенном графе. В любом разделенном графе должна быть верна одна из следующих трех возможностей:^[10]

Существует вершина Икс в я такой, что C ∪ {Икс} завершено. В этом случае, C ∪ {Икс} - максимальная клика и я - максимально независимое множество.
Существует вершина Икс в C такой, что я ∪ {Икс} не зависит. В этом случае, я ∪ {Икс} - максимальное независимое множество и C это максимальная клика.
C является максимальной кликой и я - максимальное независимое множество. В этом случае, грамм имеет уникальный раздел (C,я) в клику и независимое множество, C - максимальная клика, а я - максимальное независимое множество.

Некоторые другие проблемы оптимизации, которые НП-полный на более общие семейства графов, включая раскраска графика, аналогичным образом просты и на расщепленных графах. Нахождение Гамильтонов цикл останки НП-полный даже для разбитых графов, которые сильно хордовые графы.^[11] Также хорошо известно, что проблема минимального доминирующего множества остается НП-полный для разбитых графов.^[12]

Последовательности степеней

Одно замечательное свойство расщепленных графов заключается в том, что их можно распознать только по их последовательности степеней. Пусть последовательность степеней графа грамм быть d₁ ≥ d₂ ≥ ... ≥ d_п, и разреши м быть наибольшим значением я такой, что d_я ≥ я - 1. Тогда грамм является расщепленным графом тогда и только тогда, когда

{ displaystyle sum _ {i = 1} ^ {m} d_ {i} = m (m-1) + sum _ {i = m + 1} ^ {n} d_ {i}.}

Если это так, то м вершины с наибольшими степенями образуют максимальную клику в грамм, а остальные вершины составляют независимое множество.^[13]

Подсчет разделенных графов

Ройл (2000) показало, что п-вершинные расщепленные графы с п находятся в индивидуальная переписка с определенными Семьи Спернер. Используя этот факт, он определил формулу для количества неизоморфных расщепленных графов на п вершины. Для малых значений п, начиная с п = 1, эти числа

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (последовательность A048194 в OEIS ).

Этот перечислительный результат был также доказан ранее Тышкевич и Черняк (1990).

Примечания

^ Földes & Hammer (1977a) имели более общее определение, в которое графы, которые они называли разбитыми графами, также включали двудольные графы (то есть графы, которые можно разбить на два независимых множества) и дополняет двудольных графов (то есть графов, которые можно разбить на две клики). Földes & Hammer (1977b) используйте данное здесь определение, которому следовали в последующей литературе; например, это Brandstädt, Le & Spinrad (1999), Определение 3.2.3, стр.41.
^ Földes & Hammer (1977a); Голумбик (1980), Теорема 6.3, с. 151.
^ Голумбик (1980), Теорема 6.1, с. 150.
^ Földes & Hammer (1977a); Голумбик (1980), Теорема 6.3, с. 151; Brandstädt, Le & Spinrad (1999), Теорема 3.2.3, с. 41.
^ Макморрис и Шиер (1983); Восс (1985); Brandstädt, Le & Spinrad (1999), Теорема 4.4.2, с. 52.
^ Бендер, Ричмонд и Вормальд (1985).
^ Földes & Hammer (1977b); Голумбик (1980), Теорема 9.7, стр. 212.
^ Brandstädt, Le & Spinrad (1999), Следствие 7.1.1, с. 106, и теорема 7.1.2, с. 107.
^ Кезды, Сневилы и Ван (1996).
^ Хаммер и Симеоне (1981); Голумбик (1980), Теорема 6.2, с. 150.
^ Мюллер (1996)
^ Бертосси (1984)
^ Хаммер и Симеоне (1981); Тышкевич (1980); Тышкевич, Мельников и Котов (1981); Голумбик (1980), Теорема 6.7 и следствие 6.8, с. 154; Brandstädt, Le & Spinrad (1999), Теорема 13.3.2, с. 203. Меррис (2003) далее исследует последовательности степеней разделенных графов.

дальнейшее чтение

Глава о разделенных графах появилась в книге автора Мартин Чарльз Голумбик, «Алгоритмическая теория графов и совершенные графы».

[1] Földes & Hammer (1977a) имели более общее определение, в которое графы, которые они называли разбитыми графами, также включали двудольные графы (то есть графы, которые можно разбить на два независимых множества) и дополняет двудольных графов (то есть графов, которые можно разбить на две клики). Földes & Hammer (1977b) используйте данное здесь определение, которому следовали в последующей литературе; например, это Brandstädt, Le & Spinrad (1999), Определение 3.2.3, стр.41.

[2] Földes & Hammer (1977a); Голумбик (1980), Теорема 6.3, с. 151.

[3] Голумбик (1980), Теорема 6.1, с. 150.

[4] Földes & Hammer (1977a); Голумбик (1980), Теорема 6.3, с. 151; Brandstädt, Le & Spinrad (1999), Теорема 3.2.3, с. 41.

[5] Макморрис и Шиер (1983); Восс (1985); Brandstädt, Le & Spinrad (1999), Теорема 4.4.2, с. 52.

[6] Бендер, Ричмонд и Вормальд (1985).

[7] Földes & Hammer (1977b); Голумбик (1980), Теорема 9.7, стр. 212.

[8] Brandstädt, Le & Spinrad (1999), Следствие 7.1.1, с. 106, и теорема 7.1.2, с. 107.

[FOOTNOTEKézdySnevilyWang1996-9] Кезды, Сневилы и Ван (1996).

[10] Хаммер и Симеоне (1981); Голумбик (1980), Теорема 6.2, с. 150.

[11] Мюллер (1996)

[12] Бертосси (1984)

[13] Хаммер и Симеоне (1981); Тышкевич (1980); Тышкевич, Мельников и Котов (1981); Голумбик (1980), Теорема 6.7 и следствие 6.8, с. 154; Brandstädt, Le & Spinrad (1999), Теорема 13.3.2, с. 203. Меррис (2003) далее исследует последовательности степеней разделенных графов.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]