<<
>>

Задача

Для заданного ненаправленного графа G = (V, E) разрез определяется как раз- биение V на два непустых подмножестваA и B. Ранее, при рассмотрении сетевых потоков, мы работали с похожим определением разреза s-t.
тогда для направлен- ного графа G = (V, E) с выделенными узлами источника и стока s и t, разрез s-t определялся как разбиение V на такие множества A и B, что s A и t B. Наше новое определение отличается от того. граф стал ненаправленным, и в нем нет ни источника, ни стока.

Для разреза (A, B) в ненаправленном графе G размер (A, B) равен количеству ребер, один конец которых принадлежит A, а другой принадлежит B. Глобальным минимальным разрезом называется разрез минимального размера. Термин «глобаль- ный» указывает на то, что разрешены любые разрезы графа; нет ни источника, ни стока. Таким образом, глобальный минимальный разрез может рассматриваться как естественная характеристика «надежности»; это минимальное количество ре- бер, удаление которых приводит к потере связности графом.

Сначала мы убедимся в том, что методы сетевого потока действительно достаточны для нахождения глобального минимального разреза.

(13.4) Существует алгоритм с полиномиальным временем для нахождения глобального минимального разреза в ненаправленном графе G.

Доказательство. Начнем со сходства разрезов в ненаправленных графах и раз- резов s-t в направленных графах и с того факта, что нам известен оптимальный способ нахождения последних.

Заданный ненаправленный граф G = (V, E) необходимо преобразовать так, чтобы в нем были направленные ребра, источник и сток. Каждое ненаправленное ребро e = (и, v) E заменяется двумя противоположно ориентированными на- правленными ребрами, e' = (u, v) и e" = (v, u), каждое из которых имеет пропускную способность 1. Обозначим полученный направленный граф G'.

Теперь допустим, что мы выбрали два произвольных узла s, t e V и нашли минимальный разрез s-t в G'. Легко убедиться в том, что если (A, B) является минимальным разрезом в G', то (A, B) также является разрезом минимального размера в G среди всех разрезов, отделяющих s от t. Но мы знаем, что глобальный минимальный разрез в G должен отделять s от чего-то, так как обе стороны A и B не пусты, и s принадлежит только одной из них. Соответственно мы фиксируем

любой узел 5

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

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

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