Наименьший k-разрез

Наименьший k-разрез — это задача комбинаторной оптимизации, в которой требуется найти множество рёбер, удаление которых разбивает граф на k связных компонент. Эти рёбра называются k-разрезом. Целью задачи является поиск k-разреза с минимальным весом. Такое разбиение может иметь приложения при разработке СБИС, интеллектуальном анализе данных, в методе конечных элементов и информационном обмене при параллельных вычислениях.

Формальное определениеПравить

Если задан неориентированный граф G = (V, E) с заданными весами для рёбер w: E → N и целое число k ∈ {2, 3, …, |V|}, разбиение V на k непересекающихся множеств F = {C₁, C₂, …, C_k}, для которых минимизируется

$\underset{i=1}{\overset{k-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}\underset{j=i+1}{\overset{k}{\sum <!--\; \sum \; -->}}\underset{\begin{array}{c}{v}_1\in <!--\; \in \; -->C_i\\ v_2\in <!--\; \in \; -->C_j\end{array}}{\sum <!--\; \sum \; -->}w(\left\{v_1,v_2\right\})$$\sum _{i=1}^{k-1}\sum _{j=i+1}^{k}\sum _{\begin{smallmatrix}v_{1}\in C_{i}\\v_{2}\in C_{j}\end{smallmatrix}}w(\left\{v_{1},v_{2}\right\})$ 

Для фиксированного k задача разрешима за полиномиальное время O(|V|^k2) . Однако задача является NP-полной, если k является частью входных данных. Задача также NP-полна, если мы фиксируем $k$$k$  вершин и пытаемся найти наименьший $k$$k$ -разрез, который разделяет эти вершины

АппроксимацииПравить

Существуют некоторые аппроксимационные алгоритмы с аппроксимацией 2 − 2/k. Простой жадный алгоритм, который даёт такой коэффициент аппроксимации, вычисляет наименьший разрез в каждой связной компоненте и удаляет самый лёгкий из них. Алгоритм требует суммарно n − 1 вычислений максимального потока. Другой алгоритм, дающий тот же коэффициент, использует представление дерева Гомори — Ху^[en] наименьших разрезов. Построение дерева Гомори — Ху требует n − 1 вычислений максимального потока, но алгоритм требует в общей сложности O(kn) вычислений максимального потока. Всё же проще анализировать аппроксимационный коэффициент втотого алгоритма.

Если мы ограничиваемся графами в метрическом пространстве, предполагая, что соответствующий полный граф удовлетворяет неравенству треугольника, и если будем требовать, чтобы результирующие разбиения имели заданные заранее размеры, задача аппроксимируется с коэффициентом 3 для любого фиксированного k. Точнее, были обнаружены приближенные схемы полиномиального времени (PTAS) для таких задач.

См. такжеПравить

• Максимальный разрез графа
• Наименьший разрез