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

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

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

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

$\sum _{i=1}^{k-1}\sum _{j=i+1}^k\sum _{\begin{array}{c}{v}_1\in C_i\\ v_2\in C_j\end{array}}w(\{v_1,v_2\})$

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

Аппроксимации

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга Шаблон:Wayback
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга