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

Одним из примеров является задача о минимальном разрезе с линейным расположением. В этой задаче цель заключается в упорядочении вершин заданного n-вершинного графа G от 1 до и таким образом, чтобы минимизировать емкость наибольшего из разрезов ({1, 2, ..., i}, {i + 1, ..., n}), i <math>\in</math> [1, n]. При наличии p-аппроксимации задачи о сбалансированном разделителе, следующий алгоритм «разделяй и властвуй» дает <math>O(\rho \; log \; n)</math>-аппроксимацию задачи о минимальном разрезе с линейным упорядочением: следует найти сбалансированный сепаратор в графе, затем рекурсивно упорядочить две части и объединить эти упорядочения. Аппроксимация следует из того, что если в графе имеется сбалансированный сепаратор с расширением <math>\alpha_c(G)</math>, то на каждом уровне разрезается только <math>O(\rho n \alpha_n(G))</math> ребер, а учитывая, что сбалансированный сепаратор вычисляется на каждом шаге, количество уровней рекурсии составляет не более O(log n).