Задача
Для разреза (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
Еще по теме Задача:
- ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
- ЗАДАЧА
- ЗАДАЧА: РЕШЕНИЕ
- Основные задачи.
- в) Задачи
- в) Задачи
- ПСИХОАНАЛИЗ: ЗАДАЧА
- ЗАДАЧА ДВИГАТЕЛЬНАЯ
- Основные задачи
- Правило решаемой психологической задачи.
- Задачи и упражнения
- Терапевтическая задача