Русская Википедия:Расщепляемый граф
В теории графов расщепляемым графом называется граф, в котором вершины можно разделить на клику и независимое множество. Расщепляемые графы впервые изучали Фёлдес и ХаммерШаблон:SfnШаблон:Sfn, и независимо ввели Тышкевич и ЧернякШаблон:Sfn[1].
Расщепляемый граф может иметь несколько разложений на клику и независимое множество. Так, путь a-b-c является расщепляемым и может быть разбит тремя разными способами:
- клика {a,b} и независимое множество {c}
- клика {b,c} и независимое множество {a}
- клика {b} и независимое множество {a,c}
Расщепляемые графы можно охарактеризовать в терминах их запрещённых подграфов — граф расщепляем в том и только в том случае, когда никакой порождённый подграф не является циклом с четырьмя или пятью вершинами, а также нет пары несвязных вершин (то есть дополнения цикла из 4 вершин)[2][3].
Связь с другими семействами графов
По определению, класс расщепляемых графов замкнут по отношению к операции дополнения[4]. Ещё одна характеристика расщепляемых графов, вовлекающая дополнение — это хордальные графы, дополнения которых также хордальны[5]. Поскольку хордальные графы являются графами пересечений поддеревьев деревьев, расщепляемые графы являются графами пересечений различных подзвёзд звёзд[6]. Почти все хордальные графы являются расщепляемыми графами. То есть, при стремлении n к бесконечности, частное от числа хордальных графов с n вершинами к числу разделяемых графов стремится к единице[7].
Поскольку хордальные графы являются совершенными, то расщепляемые графы тоже совершенны. Двойные расщепляемые графы, семейство графов, полученных из расщепляемых графов удвоением числа вершин (так что клика даёт антисочетание — множество рёбер, находящихся на расстоянии не более 2 друг от друга, а независимое множество превращается в паросочетание), появляется как один из пяти основных классов совершенных графов, из которых можно построить все остальные в доказательство строгой теоремы о совершенных графахШаблон:Sfn.
Если граф и расщепляемый и интервальный, то его дополнение является и расщепляемым, и графом сравнимости, и наоборот. Расщепляемые графы сравнимости, а следовательно и расщепляемые интервальные графы, можно описать в терминах трёх запрещённых подграфов[8]. Расщепляемые кографы — это в точности пороговые графы, а расщепляемые графы перестановки — это в точности интервальные графы, дополнения которых тоже являются интервальными[9]. Шаблон:Нп5 расщепляемых графов равно 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-полные на более общих семействах графов, включая раскраску, решаются просто на расщепляемых графах.
Последовательности степеней
Одно из замечательных свойств расщепляемых графов — это то, что они могут быть распознаны чисто по их последовательностям степеней вершин. Пусть d1 ≥ d2 ≥ … ≥ dn — последовательность степеней вершин графа G и m — наибольшее значение i, для которого di ≥ i — 1. Тогда G является расщепляемым графом в том и только в том случае, когда
- <math>\sum_{i=1}^m d_i = m(m-1) + \sum_{i=m+1}^n d_i.</math>
Если это выполняется, то m вершин с наибольшими степенями образуют максимальную клику G, а оставшиеся вершины дадут независимое множество[11].
Подсчёт расщепляемых графов
РойлШаблон:Sfn показал, что расщепляемые графы с n вершинами один к одному соответствуют некоторым Шаблон:Не переведено 5. Используя этот факт он нашёл формулу числа (неизоморфных) расщепляемых графов с n вершинами. Для малых значений n, начиная с n = 1, эти числа равны
- 1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, … Шаблон:OEIS.
Это перечисление ранее доказали Тышкевич и ЧернякШаблон:Sfn.
Примечания
Литература
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
Дальнейшее чтение
- Главу о расщепляемых графах можно прочесть в книге Мартина Чарльза Голумбика (Martin Charles Golumbic) «Algorithmic Graph Theory and Perfect Graphs».
- ↑ Фёлдес и ХаммерШаблон:Sfn0 дали более общее определение, в котором графы, которые они называют расщепляемыми, включают также двудольные графы (то есть, графы, разбитые на два независимых множества) и дополнения двудольных графов (то есть, графы, которые можно разложить на две клики). Фёлдер и Хаммер Шаблон:Sfn0 дают определение, приведённое здесь и которое используются в последующей литературе, например у Брандштэдта, Ли и СпинрадаШаблон:Sfn0
- ↑ Шаблон:Harvnb; Шаблон:Harvnb, теорема 6.3, стр. 151.
- ↑ Шаблон:Статья
- ↑ Шаблон:Harvnb, теорема 6.1, стр. 150.
- ↑ Шаблон:Harvnb; Шаблон:Harvnb, теорема 6.3, стр. 151; Шаблон:Harvnb, теорема 3.2.3, p. 41.
- ↑ Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb, теорема 4.4.2, стр. 52.
- ↑ Шаблон:Harvnb.
- ↑ Шаблон:Harvnb; Шаблон:Harvnb, теорема 9.7, стр. 212.
- ↑ Шаблон:Harvnb, следствие 7.1.1 стр. 106 и теорема 7.1.2 стр. 107.
- ↑ Шаблон:Harvnb; Шаблон:Harvnb, теорема 6.2, стр. 150.
- ↑ Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb, теорема 6.7 и следствие 6.8, стр. 154; Шаблон:Harvnb, теорема 13.3.2, стр. 203. Шаблон:Harvnb дальнейшее рассмотрение последовательности степеней расщепляемых графов.
