Сепараторы в графах: различия между версиями

(Большая часть посвященных этой теме работ затрагивает либо однородную, либо общую неоднородную версии, нередко называя их просто «задачами о неплотном сечении»).

'''Теорема 1. Существует алгоритм с полиномиальным временем исполнения, который для заданного взвешенного графа <math>G = (v, E, c, \pi), b \le 1/2 \;</math> и <math>b' < min \{ b, 1/3 \} \;</math> находит b'-сбалансированное сечение с весом в O((log n)/(b — b')) больше веса минимального b-сбалансированного сечения.'''

Алгоритм решает задачу нахождения самого неплотного сечения на заданном графе, отбрасывает сегмент с меньшим весом и рекурсивно повторяет операцию на сегменте с большим весом до тех пор, пока вес обоих сегментов самого неплотного сечения не достигнет значения <math>(1 — b') \pi (G) \;</math> или меньше. Теперь сегмент с большим весом, полученный в результате сечения на последней итерации, возвращается алгоритмом как один из сегментов сбалансированного сечения, а все остальные фрагменты графа – как второй сегмент. Поскольку сама по себе задача нахождения самого неплотного сечения является NP-полной, Лейтону и Рао вначале потребовался алгоритм аппроксимации для ее решения.