Расщеплённость неориентированного графа измеряет расстояние графа от расщепляемого графа. Расщепляемый граф — это граф, вершины которого могут быть разделены на независимое множество (без рёбер внутри этого множества) и клику (имеющую все возможные рёбра в этом подмножестве). Расщеплённость — это наименьшее число рёбер, удаление и добавление которых преобразует данный граф в расщепляемый граф.
Расчет по последовательности степеней Расщеплённость графа может быть вычислена исходя только из последовательности степеней графа без детального исследования структуры графа. Пусть будет графом с вершинами, степени которого в убывающем порядке есть . Пусть будет максимальным индексом, для которого . Тогда расщеплённость графа равна
Заданный граф является уже расщепляемым графом, если . В противном случае граф может быть преобразован в расщепляемый граф путём вычисления , добавления всех недостающих рёбер между парами вершин с максимальной степенью и удаления всех рёбер между парами остальных вершин. Таким образом, расщеплённость и последовательность добавления и удаления рёбер может быть вычислена за линейное время.
Приложения Расщеплённость графа используется в как параметр для описания эффективности алгоритмов. Например, раскраска графов является фиксированно-параметрически разрешимой по этому параметру — можно раскрасить оптимально графы с ограниченной расщеплённостью за линейное время.
Примечания
Категория:Инварианты графов