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

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

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

${\displaystyle \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) ^[1]. Однако задача является NP-полной, если k является частью входных данных^[2]. Задача также NP-полна, если мы фиксируем ${\displaystyle k}$ вершин и пытаемся найти наименьший ${\displaystyle k}$-разрез, который разделяет эти вершины ^[3]

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

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

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

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (19 июня 2017) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (19 июня 2017) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.