В теории графов расщепляемым графом называется граф, в котором вершины можно разделить на клику и независимое множество. Расщепляемые графы впервые изучали Фёлдес и Хаммер, и независимо ввели Тышкевич и ЧернякФёлдес и Хаммер дали более общее определение, в котором графы, которые они называют расщепляемыми, включают также двудольные графы (то есть, графы, разбитые на два независимых множества) и дополнения двудольных графов (то есть, графы, которые можно разложить на две клики). Фёлдер и Хаммер дают определение, приведённое здесь и которое используются в последующей литературе, например у Брандштэдта, Ли и Спинрада.

Расщепляемый граф может иметь несколько разложений на клику и независимое множество. Так, путь a-b-c является расщепляемым и может быть разбит тремя разными способами: клика {a,b} и независимое множество {c} клика {b,c} и независимое множество {a} клика {b} и независимое множество {a,c}

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

Связь с другими семействами графов По определению, класс расщепляемых графов замкнут по отношению к операции дополнения, теорема 6.1, стр. 150.. Ещё одна характеристика расщепляемых графов, вовлекающая дополнение — это хордальные графы, дополнения которых также хордальны; , теорема 6.3, стр. 151; , теорема 3.2.3, p. 41.. Поскольку хордальные графы являются графами пересечений поддеревьев деревьев, расщепляемые графы являются графами пересечений различных подзвёзд звёзд; ; , теорема 4.4.2, стр. 52.. Почти все хордальные графы являются расщепляемыми графами. То есть, при стремлении n к бесконечности, частное от числа хордальных графов с n вершинами к числу разделяемых графов стремится к единице..

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

Если граф и расщепляемый и интервальный, то его дополнение является и расщепляемым, и графом сравнимости, и наоборот. Расщепляемые графы сравнимости, а следовательно и расщепляемые интервальные графы, можно описать в терминах трёх запрещённых подграфов; , теорема 9.7, стр. 212.. Расщепляемые кографы — это в точности пороговые графы, а расщепляемые графы перестановки — это в точности интервальные графы, дополнения которых тоже являются интервальными, следствие 7.1.1 стр. 106 и теорема 7.1.2 стр. 107.. расщепляемых графов равно 2.

Максимальная клика и максимальное независимое множество Пусть G — расщепляемый граф, разложенный на клику C и независимое множество I. Тогда любая максимальная клика в расщеплённом графе либо совпадает с C, либо является окрестностью вершины из I. Таким образом, в расщепляемом графе легко найти максимальную клику и, кроме того, максимальное независимое множество . В любом расщепляемом графе должно выполняться одно из следующих утверждений; , теорема 6.2, стр. 150.: Существует вершина 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 является расщепляемым графом в том и только в том случае, когда

Если это выполняется, то m вершин с наибольшими степенями образуют максимальную клику G, а оставшиеся вершины дадут независимое множество; ; ; , теорема 6.7 и следствие 6.8, стр. 154; , теорема 13.3.2, стр. 203. дальнейшее рассмотрение последовательности степеней расщепляемых графов..

Подсчёт расщепляемых графов Ройл показал, что расщепляемые графы с n вершинами один к одному соответствуют некоторым . Используя этот факт он нашёл формулу числа (неизоморфных) расщепляемых графов с n вершинами. Для малых значений n, начиная с n = 1, эти числа равны 1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, … . Это перечисление ранее доказали Тышкевич и Черняк.

Примечания

Литература

Дальнейшее чтение Главу о расщепляемых графах можно прочесть в книге Мартина Чарльза Голумбика (Martin Charles Golumbic) «Algorithmic Graph Theory and Perfect Graphs».

Категория:Семейства графов Категория:Графы пересечений Категория:Совершенные графы