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

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

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

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

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

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

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

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

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

Алгоритмические проблемы [ править ]

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

  1. Там существует вершина х в Я таким образом, что С ∪ { х } является полным. В этом случае C ∪ { x } - максимальная клика, а I - максимальное независимое множество.
  2. Там существует вершина х в С таким образом, что я ∪ { х } является независимым. В этом случае I ∪ { x } - максимальное независимое множество, а C - максимальная клика.
  3. 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]

Подсчет разделенных графиков [ править ]

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

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

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

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

  1. ^ Фёльдес и Хаммер (1977a) дали более общее определение, в котором графы, которые они называли разбитыми графами, также включали двудольные графы (то есть графы, которыеделятсяна два независимых множества) и дополнения к двудольным графам (то есть графы, которые можно разделить на две клики). Földes & Hammer (1977b) используют данное здесь определение, которому следовали в последующей литературе; например, это Brandstädt, Le & Spinrad (1999) , Определение 3.2.3, стр. 41.
  2. ^ Földes & Молот (1977a) ; Голумбик (1980) , теорема 6.3, с. 151.
  3. ^ Голумбик (1980) , теорема 6.1, стр. 150.
  4. ^ Földes & Молот (1977a) ; Голумбик (1980) , теорема 6.3, с. 151; Brandstädt, Le & Spinrad (1999) , теорема 3.2.3, с. 41.
  5. ^ МсМогпз & Shier (1983) ; Восс (1985) ; Brandstädt, Le & Spinrad (1999) , теорема 4.4.2, с. 52.
  6. ^ Bender, Richmond & Wormald (1985) .
  7. ^ Földes & Молот (1977b) ; Голумбик (1980) , теорема 9.7, стр. 212.
  8. ^ Brandstädt, Le & Спинрад (1999) , следствие 7.1.1, стр. 106, и теорема 7.1.2, с. 107.
  9. ^ Kézdy, Snevily & Wang (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. Merris (2003) далее исследует последовательности степеней разделенных графов.

Ссылки [ править ]

  • Бендер, Э.А.; Ричмонд, LB; Wormald, NC (1985), «Почти все хордовые графы расщепляются», J. Austral. Математика. Soc. , А, 38 (2): 214-221, DOI : 10,1017 / S1446788700023077 , МР  0770128.
  • Бертосси, Алан А. (1984), "Доминирующие множества для расщепленных и двудольных графов", Письма об обработке информации , 19 : 37-40, DOI : 10.1016 / 0020-0190 (84) 90126-1.
  • Брандштадт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 0-89871-432-X.
  • Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), "Сильная совершенная теорема графа", Анналы математики , 164 (1): 51-229, Arxiv : математика / 0212070 , DOI : 10,4007 / annals.2006.164.51 , MR  2233847.
  • Фёльдес, Стефан; Хаммер, Питер Лэдислав (1977a), «Сплит-графы», Труды восьмой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Университет штата Луизиана, Батон-Руж, штат Луизиана, 1977) , Congressus Numerantium, XIX , Виннипег: Utilitas Math ., стр. 311–315, MR  0505860.
  • Фёльдес, Стефан; Молоток, Питер Ладислав (1977b), "Split графы , имеющий Дилуорс номер два", Canadian Journal математики , 29 (3): 666-672, DOI : 10,4153 / CJM-1977-069-1 , MR  0463041.
  • Голумбик, Мартин Чарльз (1980), теория алгоритмических графов и совершенные графы , Academic Press, ISBN 0-12-289260-7, Руководство по ремонту  0562306.
  • Хаммер, Питер Лэдислав ; Симеон, Бруно (1981), "О splittance графа", Combinatorica , 1 (3): 275-284, DOI : 10.1007 / BF02579333 , МР  0637832.
  • Kézdy, André E .; Сневилый, Хантер С .; Ван Чи (1996), "Partitioning перестановок в увеличении и уменьшении подпоследовательности", Журнал комбинаторной теории , Series A , 73 (2): 353-359, DOI : 10.1016 / S0097-3165 (96) 80012-4 , МР  1370138.
  • Макморрис, Франция; Shier, DR (1983), «Представление хордовых графов на K 1, n », Commentationes Mathematicae Universitatis Carolinae , 24 : 489–494, MR  0730144.
  • Merris, Рассел (2003), "Split графика", Европейский журнал комбинаторика , 24 (4): 413-430, DOI : 10.1016 / S0195-6698 (03) 00030-1 , MR  1975945.
  • Мюллер, Haiko (1996), "Гамильтоновы схемы в Хордовых двудольных графах", дискретная математика , 156 : 291-298, DOI : 10.1016 / 0012-365x (95) 00057-4.
  • Ройл, Гордон Ф. (2000), «Подсчет покрытий и разбиение графов» (PDF) , Журнал целочисленных последовательностей , 3 (2): 00.2.6, MR  1778996.
  • Тышкевич, Регина И. (1980), «[Каноническое разложение графа]», Доклады АН СССР , 24 : 677–679, МР  0587712.
  • Тышкевич Регина И .; Черняк А.А. Каноническое разбиение графа, определяемое степенями его вершин, Изв. Акад. Наук БССР, сер. Физ.-мат. Наук , 5 : 14–26, МР  0554162..
  • Тышкевич Регина И .; Черняк, А.А. (1990),Еще один метод перечисления непомеченных комбинаторных объектов, Мат. Заметки (на русском языке ), 48 (6): 98-105, MR  1102626. Переведено как «Еще один метод перечисления немаркированных комбинаторных объектов» (1990), Математические заметки АН СССР 48 (6): 1239–1245, doi : 10.1007 / BF01240267 .
  • Тышкевич Регина И .; Мельников, О.И. Котов В.М. (1981), "О графах и последовательностях степеней: каноническая декомпозиция", Кибернетика , 6 : 5–8, MR  0689420.
  • Восс, Х.-Дж. (1985), «Примечание к статье МакМорриса и Шира», Commentationes Mathematicae Universitatis Carolinae , 26 : 319–322, MR  0803929.

Дальнейшее чтение [ править ]

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