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

Даже если все веса (ребер и вершин) равны 1, нахождение b-сбалансированного сечения с минимальным весом представляет собой NP-полную задачу (для b = 1/2 она превращается в задачу [[бисекция графа|бисекции графа]]). Лейтон и Рао [23, 24] предложили алгоритм псевдоаппроксимации для решения задачи общего вида.

'''Теорема 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-полной, Лейтону и Рао вначале потребовался алгоритм аппроксимации для ее решения.

'''Теорема 2. Существует алгоритм нахождения самого неплотного сечения для материальных потоков (задача 2) с полиномиальным временем исполнения и коэффициентом аппроксимации O (log p), где p обозначает количество вершин графа с ненулевым весом.'''