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

Эта статья о графах, которые можно разделить на клику и независимое множество. Информацию о разрезах, образующих полные двудольные графы, см. в разделе « Разбиение (теория графов)» .

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

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

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

1. клика { a , b } и независимое множество { c }
2. клика { b , c } и независимое множество { a }
3. клика { b } и независимое множество { a , c }

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

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

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

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

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

Алгоритмические задачи

Пусть G — расщепляемый граф, разбитый на клику C и независимое множество i . Тогда каждая максимальная клика в расщепленном графе является либо самой C , либо окрестностью вершины в i . Таким образом, легко определить максимальную клику и, дополнительно, максимальное независимое множество в расщепленном графе. В любом разделенном графе должна быть истинна одна из следующих трех возможностей:

1. Существует вершина x в i такая, что C ∪ { x } полно. В этом случае C ∪ { x } — максимальная клика, а i — максимальное независимое множество.
2. существует вершина x В C такая, что i ∪ { x } независима. В этом случае i ∪ { x } — максимальное независимое множество, а C — максимальная клика.
3. C — максимальная клика, а i — максимальное независимое множество. В этом случае G имеет единственное разбиение ( C , i ) на клику и независимое множество, C — максимальная клика, а i — максимальное независимое множество.

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

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

Одним из замечательных свойств разделенных графов является то, что их можно распознать исключительно по последовательностям степеней . Пусть последовательность степеней графа G равна d ₁ ≥ d ₂ ≥ … ≥ d _n , и пусть m — наибольшее значение i такое, что d _i ≥ i – 1 . Тогда G является расщепляемым графом тогда и только тогда, когда

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

Если это так, то m вершин с наибольшей степенью образуют максимальную клику в G , а остальные вершины составляют независимое множество.

Расщепление произвольного графа измеряет степень , в которой это неравенство не выполняется. Если граф не является расщепленным графом, то наименьшую последовательность вставок и удалений ребер, которая превращает его в расщепленный граф, можно получить, добавив все недостающие ребра между m вершинами с наибольшей степенью и удалив все ребра между парами графа. оставшиеся вершины; расщепление подсчитывает количество операций в этой последовательности.

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

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

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

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

Ссылки

• Бендер, Е.А.; Ричмонд, LB; Вормальд, Северная Каролина (1985), «Почти все хордальные графы расщепляются», J. Austral. Математика. Соц. , А, 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-Х .
• Чудновская Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе», Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , doi : 10.4007/annals.2006.164.51 , MR   2233847 .
• Фёлдес, Стефан; Хаммер, Питер Ладислав (1977a), «Расщепление графов», Труды Восьмой Юго-восточной конференции по комбинаторике, теории графов и вычислениям (Университет штата Луизиана, Батон-Руж, Луизиана, 1977) , Congressus Numerantium, vol. XIX, Виннипег: Utilitas Math., стр. 311–315, MR   0505860 .
• Фёлдес, Стефан; Хаммер, Питер Ладислав (1977b), «Разделенные графы, имеющие номер Дилворта два», Canadian Journal of Mathematics , 29 (3): 666–672, doi : 10.4153/CJM-1977-069-1 , MR   0463041 .
• Голумбик, Мартин Чарльз (1980), алгоритмическая теория графов и совершенные графы , Academic Press, ISBN  0-12-289260-7 , МР   0562306 .
• Хаммер, Питер Ладислав ; Симеоне, Бруно (1981), «Расщепление графа», Combinatorica , 1 (3): 275–284, doi : 10.1007/BF02579333 , MR   0637832 .
• Кезди, Андре Э.; Сневили, Хантер С.; Ван, Чи (1996), «Разбиение перестановок на возрастающие и убывающие подпоследовательности», Журнал комбинаторной теории , серия A , 73 (2): 353–359, doi : 10.1016/S0097-3165(96)80012-4 , MR   1370138 .
• МакМоррис, Франция; Шир, Д. Р. (1983), «Представление хордальных графов на K _{1, n} », Математические заметки Университета Каролины , 24 : 489–494, MR   0730144 .
• Меррис, Рассел (2003), «Разделение графов», European Journal of Combinatorics , 24 (4): 413–430, doi : 10.1016/S0195-6698(03)00030-1 , MR   1975945 .
• Мюллер, Хайко (1996), «Гамильтоновы схемы в хордальных двудольных графах», Discrete Mathematics , 156 : 291–298, doi : 10.1016/0012-365x(95)00057-4 .
• Ройл, Гордон Ф. (2000), «Подсчет покрытий множеств и расщепление графов» (PDF) , Журнал целочисленных последовательностей , 3 (2): 00.2.6, MR   1778996 .
• Тышкевич, Регина И. (1980), "[Каноническое разложение графа]", Доклады Академии наук СССР , 24 : 677–679, MR   0587712
• Тышкевич Регина И. ; Черняк А.А. (1979), "Каноническое разбиение графа, определяемое степенями его вершин" Каноническое разложение графа, определяемого степенями его вершин (PDF) , Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk (in Russian), 5 : 14–26, MR  0554162 .
• Tyshkevich, Regina I. ; Черняк, AA (1990), Еще один метод перечисления непомеченных комбинаторных объектов , Мат. Заметки , 48 (6): 98–105, МР   1102626 . В переводе «Еще один метод перечисления немаркированных комбинаторных объектов» (1990), Математические записки АН СССР 48 (6): 1239–1245, дои : 10.1007/BF01240267 .
• Тышкевич Регина И. ; Мельников О.И.; Котов В.М. (1981), "О графах и последовательностях степеней: каноническая декомпозиция", Кибернетика , 6 : 5–8, MR   0689420 .
• Восс, Х.-Дж. (1985), «Примечание к статье Макморриса и Шира», Математические обзоры Университета Каролины , 26 : 319–322, MR   0803929 .

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

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