Меню Главная Случайная статья Настройки Наименьшийk-разрез Материал из https://ru.wikipedia.org Наименьший k-разрез — это задача комбинаторной оптимизации, в которой требуется найти множество рёбер, удаление которых разбивает граф на k связных компонент. Эти рёбра называются k-разрезом. Целью задачи является поиск k-разреза с минимальным весом. Такое разбиение может иметь приложения при разработке СБИС, интеллектуальном анализе данных, в методе конечных элементов и информационном обмене при параллельных вычислениях. Содержание 1 Формальное определение 2 Аппроксимации 3 См. также 4 Примечания 5 Литература Формальное определение Если задан неориентированный граф G = (V, E) с заданными весами для рёбер w: E  N и целое число k  {2, 3, …, |V|}, разбиение V на k непересекающихся множеств F = {C1, C2, …, Ck}, для которых минимизируется ${\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]. См. также Максимальный разрез графа Наименьший разрез Примечания Goldschmidt, Hochbaum, 1988. Garey, Johnson, 1979. [1] Архивная копия от 22 декабря 2015 на Wayback Machine, где процитирована статья [2] Архивная копия от 29 августа 2012 на Wayback Machine Saran, Vazirani, 1991. Vazirani, 2003, с. 40-44. Guttmann-Beck, Hassin, 1999, с. 198-207. Fernandez de la Vega, Karpinski, Kenyon, 2004. Литература O. Goldschmidt, D. S. Hochbaum. Proc. 29th Ann. IEEE Symp. on Foundations of Comput. Sci.. — IEEE Computer Society, 1988. — С. 444-451. Francesc Comellas, Emili Sapena. A multiagent algorithm for graph partitioning. Lecture Notes in Comput. Sci. // Algorithmica. — 2006. — Т. 3907. — С. 279-285. — ISSN 0302-9743. — doi:10.1007/s004530010013. Архивировано из оригинала 12 декабря 2009 года.