<<
>>

Задача

В задаче о максимальном разрезе имеется ненаправленный граф G = (V, E) с по- ложительными целочисленными весами каждого ребра e. Для разбиения (A, B) множества вершин w(A, B) обозначает общий вес ребер, один конец которых при- надлежит A, а другой принадлежит B:

w(А,В)= ]Р u\,

*Чw.r)

j| β, выполняется с ЖР-сложностью.

В то же время, конечно, задача о максимальном разрезе напоминает задачу о минимальном разрезе s-t для потоковых сетей, имеющую полиномиальное решение. Основная причина ее неразрешимости обусловлена тем фактом, что мы стремимся максими- зировать, а не минимизировать вес проходящих через разрез ребер.

И хотя задача нахождения устойчивой конфигурации сети Хопфилда не была оптимизационной задачей как таковой, мы видим, что задача о максимальном разрезе с ней тесно связана. На языке сетей Хопфилда задача о максимальном раз- резе представляет собой экземпляр, в котором все веса ребер положительны (а не отрицательны), а конфигурации состояний узлов S естественно соответствуют разбиениям (A, B): узлы имеют состояние -1 в том, и только в том случае, если они принадлежат множеству A, и состояние +1 — в том, и только в том случае, если они принадлежат множеству B. Целью является такое распределение состояний, при котором как можно большая часть веса приходится на хорошие ребра — те, у которых конечные точки находятся в разных состояниях. В такой формулиров- ке задача о максимальном разрезе направлена на максимизацию величины Ф(S), которая использовалась в доказательстве (12.3) в том случае, когда все веса ребер положительны.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии
  16. Основные задачи МПП.
  17. Задачи и упражнения