A separator - это подмножество вершин, удаление которых оставляет график с несколькими связанными компонентами.Разделитель равен сбалансированный , если каждый связанный компонент имеет меньше половины числа вершин по сравнению с исходным графом.
График с малой шириной линии имеет небольшой сбалансированный разделитель.Точнее, график ширины дерева k имеет сбалансированный разделитель с максимум k + 1 вершинами.
Алгоритмы используют это следующим образом:
удалить небольшой сбалансированный разделитель изграфик
рекурсивно найти оптимальное решение для подключенных компонентов
снова добавить разделитель (возможно, вершина за вершиной) и использовать решениячтобы подключенные компоненты могли найти оптимальное решение для всего графика.
Чтобы сделать приведенную выше схему эффективной, необходимо выполнить несколько требований:
разделитель на первом шаге мал (то есть имеет постоянный размер)
связанные компоненты на втором шаге имеют существенно меньшее количество вершин, чем исходный граф (то естьесть постоянная дробь, например 1/2).
вышеупомянутые свойства наследуются индуцированным подграфам (в противном случае вы не можете выполнить рекурсивный поиск)
Частичные оптимальные решения для подключенных компонентов могут быть эффективно объединены в оптимальное решение для всего графика
Этим требованиям соответствуют графики с малой шириной дерева - кроме последнего: это конкретноедля каждой задачи оптимизации, и именно об этом разработчики алгоритмов написали исследовательские работы.
(Изображение взято из статьи в Википедии о разделитель вершин .)