Граф, который разбивается на клику и независимое множество
Разделенный граф, разделенный на клику и независимое множество.
В теории графов , разделе математики, расщепляемый граф — это граф , в котором вершины могут быть разделены на клику и независимое множество . Расщепляемые графы были впервые изучены Фёльдесом и Хаммером (1977a, 1977b) , и независимо введены Тышкевичем и Черняком (1979), где они назвали эти графы «полярными графами» . [ 1 ]
Разделенный граф может иметь более одного разбиения на клику и независимое множество; например, путь a – b – c является разделенным графом, вершины которого могут быть разделены тремя различными способами:
клика { a , b } и независимое множество { c }
клика { b , c } и независимое множество { a }
клика { b } и независимое множество { a , c }
Расщепляемые графы можно охарактеризовать с точки зрения их запрещенных индуцированных подграфов : граф является расщепляемым тогда и только тогда, когда ни один индуцированный подграф не является циклом на четырех или пяти вершинах или парой непересекающихся ребер (дополнением к 4-циклу). [2]
Связь с другими семействами графов
Из определения, расщепленные графы, очевидно, замкнуты относительно дополнения . [3] Другая характеристика расщепленных графов включает в себя дополнение: они являются хордовыми графами, дополнения которых также являются хордовыми. [ 4] Так же, как хордовые графы являются графами пересечений поддеревьев деревьев, расщепленные графы являются графами пересечений различных подзвезд звездных графов . [5] Почти все хордовые графы являются расщепленными графами; то есть в пределе, когда n стремится к бесконечности, доля n -вершинных хордовых графов, которые расщеплены, стремится к единице. [6]
Поскольку хордовые графы являются совершенными , то и расщепленные графы являются совершенными. Двойные расщепленные графы , семейство графов, полученных из расщепленных графов путем удвоения каждой вершины (таким образом, клика начинает индуцировать антисопоставление, а независимое множество начинает индуцировать сопоставление), занимают видное место как один из пяти основных классов совершенных графов, из которых могут быть сформированы все остальные в доказательстве теоремы о сильном совершенном графе, представленном Чудновским и др. (2006) .
Если граф является как графом разделения, так и графом интервалов , то его дополнение является как графом разделения, так и графом сравнимости , и наоборот. Графы сравнимости разделения, а следовательно, и графы интервалов разделения, можно охарактеризовать в терминах набора из трех запрещенных индуцированных подграфов. [7] Графы разделения являются в точности пороговыми графами . Графы перестановок разделения являются в точности графами интервалов, имеющими дополнения графов интервалов; [8]
это графы перестановок перекошенных перестановок . [9] Графы разделения имеют кохроматическое число 2.
Алгоритмические проблемы
Пусть G — расщепляемый граф, разбитый на клику C и независимое множество i . Тогда каждая максимальная клика в расщепляемом графе — это либо сама клика C , либо окрестность вершины в i . Таким образом, легко определить максимальную клику и, соответственно, максимальное независимое множество в расщепляемом графе. В любом расщепляемом графе должна быть верна одна из следующих трех возможностей: [10]
Существует вершина x в i, такая, что C ∪ { x } является полным. В этом случае C ∪ { x } является максимальной кликой, а i является максимальным независимым множеством.
Существует вершина x в C, такая что i ∪ { x } независима. В этом случае i ∪ { x } является максимальным независимым множеством, а C является максимальной кликой.
C — максимальная клика, а i — максимальное независимое множество. В этом случае G имеет уникальное разбиение ( C , i ) на клику и независимое множество, C — максимальная клика, а i — максимальное независимое множество.
Некоторые другие задачи оптимизации, которые являются NP-полными на более общих семействах графов, включая раскраску графов , также просты на расщепленных графах. Поиск гамильтонова цикла остается NP-полным даже для расщепленных графов, которые являются строго хордовыми графами . [11] Также хорошо известно, что задача минимального доминирующего множества остается NP-полной для расщепленных графов. [12]
Последовательности степеней
Одно замечательное свойство расщепленных графов заключается в том, что их можно распознать исключительно по их степенным последовательностям . Пусть степенная последовательность графа G будет d 1 ≥ d 2 ≥ … ≥ d n , и пусть m будет наибольшим значением i таким, что d i ≥ i – 1 . Тогда G является расщепленным графом тогда и только тогда, когда
Если это так, то m вершин с наибольшими степенями образуют максимальную клику в G , а оставшиеся вершины составляют независимое множество. [13]
Расщепление произвольного графа измеряет степень, в которой это неравенство не выполняется. Если граф не является расщепляемым графом, то наименьшая последовательность вставок и удалений ребер, которая превращает его в расщепляемый граф, может быть получена путем добавления всех недостающих ребер между m вершинами с наибольшими степенями и удаления всех ребер между парами оставшихся вершин; расщепляемость подсчитывает количество операций в этой последовательности. [14]
Этот перечислительный результат был также доказан ранее Тышкевичем и Черняком (1990).
Примечания
^ Фёльдес и Хаммер (1977a) дали более общее определение, в котором графы, которые они называли расщепленными графами, также включали двудольные графы (то есть графы, которые можно разбить на два независимых множества) и дополнения двудольных графов (то есть графы, которые можно разбить на две клики). Фёльдес и Хаммер (1977b) используют данное здесь определение, которому следовали в последующей литературе; например, это Brandstädt, Le & Spinrad (1999), Определение 3.2.3, стр.41.
^ Фёльдес и Хаммер (1977a); Голумбик (1980), Теорема 6.3, с. 151.
^ Голумбик (1980), Теорема 6.1, стр. 150.
^ Фёльдес и Хаммер (1977a); Голумбик (1980), теорема 6.3, с. 151; Брандштедт, Ле и Спинрад (1999), теорема 3.2.3, с. 41.
^ МакМоррис и Шир (1983); Восс (1985); Брандштедт, Ле и Спинрад (1999), теорема 4.4.2, с. 52.
^ Хаммер и Симеоне (1981); Тышкевич (1980); Тышкевич, Мельников и Котов (1981); Голумбич (1980), Теорема 6.7 и Следствие 6.8, стр. 154; Брандштедт, Ле и Спинрад (1999), Теорема 13.3.2, стр. 203. Меррис (2003) далее исследует последовательности степеней расщепленных графов.
^ Хаммер и Симеоне (1981).
Ссылки
Бендер, EA; Ричмонд, LB; Вормальд, NC (1985), «Почти все хордовые графы расщепляются», J. Austral. Math. Soc. , A, 38 (2): 214–221, doi : 10.1017/S1446788700023077 , MR 0770128.
Бертосси, Алан А. (1984), «Доминирующие множества для разделенных и двудольных графов», Information Processing Letters , 19 : 37–40, doi :10.1016/0020-0190(84)90126-1.
Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: Обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 0-89871-432-X.
Фёльдес, Стефан; Хаммер, Питер Ладислав (1977a), «Разделенные графы», Труды Восьмой юго-восточной конференции по комбинаторике, теории графов и вычислениям (Университет штата Луизиана, Батон-Руж, Луизиана, 1977) , Congressus Numerantium, т. XIX, Виннипег: Utilitas Math., стр. 311–315, MR 0505860.
Kézdy, André E.; Snevily, Hunter S.; Wang, Chi (1996), «Разбиение перестановок на возрастающие и убывающие подпоследовательности», Journal of Combinatori Theory , Series A , 73 (2): 353–359, doi : 10.1016/S0097-3165(96)80012-4 , MR 1370138.
МакМоррис, Франция; Шир, Д. Р. (1983), «Представление хордальных графов на K 1, n », Commentationes Mathematicae Universitatis Carolinae , 24 : 489–494, MR 0730144.
Меррис, Рассел (2003), «Разделенные графы», Европейский журнал комбинаторики , 24 (4): 413–430, doi : 10.1016/S0195-6698(03)00030-1 , MR 1975945.
Мюллер, Хайко (1996), «Гамильтоновы контуры в хордовых двудольных графах», Дискретная математика , 156 : 291–298, doi : 10.1016/0012-365x(95)00057-4.
Ройл, Гордон Ф. (2000), «Подсчет покрытий множеств и разделенных графов» (PDF) , Журнал целочисленных последовательностей , 3 (2): 00.2.6, MR 1778996.
Тышкевич Регина И. ; Черняк А.А. (1979), "Каноническое разбиение графа, определяемое степенями его вершин" Каноническое разложение графа, определяемого ступенями его вершины (PDF) , Изв. Акад. Наук БССР, сер. Физ.-Мат. Наук , 5 : 14–26, МР 0554162..
Тышкевич Регина И. ; Черняк А. А. (1990), Еще один метод обработки непомеченных комбинаторных объектов, Матем. Заметки , 48 (6): 98–105, МР 1102626.. Переводится как «Еще один метод перечисления немаркированных комбинаторных объектов» (1990), Математические записки АН СССР 48 (6): 1239–1245, doi :10.1007/BF01240267.
