Центрированная раскраска

Центрированная раскраска В теории графов центрированная раскраска — это тип раскраски графа, связанный с понятием глубины дерева. Минимальное количество цветов в центрированной раскраске графа равно его глубине дерева. Параметризованный вариант, q-центрированная раскраска, предоставляет способ покрытия графов небольшим числом подграфов с глубиной дерева не более q и может использоваться в алгоритмах для изоморфизма подграфов и родственных задач. Количество цветов, необходимое для q-центрированной раскраски, ограничено как функция от q в графах с ограниченным расширением.

Определение

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

q-центрированная раскраска — это центрированная раскраска с более слабым свойством: каждый связный подграф (или, что эквивалентно, каждый связный порождённый подграф) либо имеет не менее q цветов, либо имеет хотя бы одну вершину, цвет которой уникален. Для q=2 это обычная раскраска графа: каждое ребро, а следовательно, и любой больший связный подграф, должны иметь не менее двух цветов. Для q=3 q-центрированная раскраска совпадает со звездной раскраской: любой подграф только с двумя цветами должен быть несвязным объединением звёзд, центрированных в уникально окрашенных вершинах каждой компоненты. Для q>n, где n — количество вершин в графе, невозможно иметь q цветов, и q-центрированная раскраска совпадает с центрированной раскраской без параметра. Более того, всякий раз, когда q не меньше глубины дерева t данного графа, количество цветов в q-центрированной раскраске также не меньше t.

Эквивалентность с глубиной дерева

Минимальное количество цветов в центрированной раскраске данного графа G равно его глубине дерева — минимальной высоте корневого леса F на том же множестве вершин, что и G, такого, что каждое ребро в G соединяет пару предок-потомок в F. В одну сторону: если F — лес с таким свойством, центрированную раскраску с количеством цветов, равным его высоте, можно получить, сгруппировав вершины F по расстоянию от корней их деревьев и используя один цвет для каждой группы. В другую сторону: из центрированной раскраски G можно получить лес F с нужными свойствами, выбрав корень дерева с уникальным цветом в каждой компоненте связности G, причём дети каждого корня строятся рекурсивно из связных подграфов, полученных удалением корня из G.

Алгоритмическое применение

В q-центрированной раскраске каждое подмножество из k цветов, где k<q, индуцирует подграф, на котором раскраска является центрированной. Следовательно, этот индуцированный подграф имеет глубину дерева не более k. Выбирая все подмножества заданного числа цветов, любой граф с q-центрированной раскраской можно покрыть графами ограниченной глубины дерева. В частности, если нужно найти копии графа H с h вершинами как подграфы большего графа G (задача изоморфизма подграфов), и G имеет (h+1)-центрированную раскраску с k цветами, то любая копия H может использовать не более h цветов. Все копии H можно найти в подграфах G, порождённых всеми h-элементными наборами цветов. Эта идея сводит задачу изоморфизма подграфов к O(k^h) подзадачам, каждая из которых решается быстро благодаря малой глубине дерева. Та же идея применима и для проверки, моделирует ли G любую формулу первого порядка в логике графов, использующую только h переменных.

Чтобы этот метод был эффективным, важно, чтобы количество цветов k в центрированной раскраске было небольшим. Для графов с ограниченным расширением это число ограничено полиномом от k, чья (большая) степень зависит от семейства. Более общо, для графов в классификации семейств графов по мелким минорам это число составляет o(|V(G)|). Однако для классов графов, которые являются где-то плотными (то есть не нигде не плотными), такая оценка невозможна.