Меню
Главная
Случайная статья
Настройки
|
Наименьший разрез графа — это минимальный в некотором смысле разрез (разбиение вершин графа на два непересекающихся связанных множества).
Содержание
Вариации
Вариации наименьшего разреза:
- Разрез с минимальным числом рёбер среди всех разрезов данного разбиения графа на две связные компоненты. Такие разрезы порождают векторное пространство разрезов графа.
- Разрез с минимальным числом рёбер среди всех разрезов в неориентированном графе. Такой разрез определяет рёберную связность графа. Алгоритм Каргера даёт эффективный рандомизированный метод поиска такого разреза.
- Задача о наименьшем разрезе в неориентированных взвешенных графах может быть решена алгоритмом Штёр — Вагнера.
- Обобщение невзвешенного и неориентированного наименьшего разреза, наименьший k-разрез, целью которого является разбиение графа на по меньшей мере
- Разбиение графа, семейство комбинаторных задач оптимизации, в которых граф разбивается на две или больше частей с дополнительным условием балансировки размеров разреза.
- Разрез потока, который отделяет источник от стока и минимизирует суммарный вес дуг, направленных из части, содержащей источник, в часть, содержащий сток. Как показывает теорема Форда — Фалкерсона, вес такого разреза равен максимальному потоку, который может быть пропущен из источника в сток через данную сеть. Альтернативно данная вариация проблемы может быть решена посредством алгоритма Каргера.
- Разрез взвешенной неориентированной сети, который разделяет выделенную пару вершин и имеет минимальный вес. Система разрезов, которая решает задачу для любой пары вершин, может быть собрана в структуру, известную как дерево Гомори — Ху[англ.] графа.
Число наименьших разрезов
Граф с n вершинами может иметь не более различных наименьших разрезов.
См. также
Примечания
- 4 Min-Cut Algorithms (неопр.). Дата обращения: 19 июня 2017. Архивировано 5 августа 2016 года.
Литература
|
|