Наименьший разрез

Вариации наименьшего разреза:

• Разрез с минимальным числом рёбер среди всех разрезов данного разбиения графа на две связные компоненты. Такие разрезы порождают векторное пространство разрезов графа.
• Разрез с минимальным числом рёбер среди всех разрезов в неориентированном графе. Такой разрез определяет рёберную связность графа. Алгоритм Каргера даёт эффективный рандомизированный метод поиска такого разреза.
• Задача о наименьшем разрезе в неориентированных взвешенных графах может быть решена алгоритмом Штёр — Вагнера.
• Обобщение невзвешенного и неориентированного наименьшего разреза, наименьший k-разрез, целью которого является разбиение графа на по меньшей мере k связных компонент путём удаления как можно меньшего числа рёбер.
• Разбиение графа, семейство комбинаторных задач оптимизации, в которых граф разбивается на две или больше частей с дополнительным условием балансировки размеров разреза.
• Разрез потока, который отделяет источник от стока и минимизирует суммарный вес дуг, направленных из части, содержащей источник, в часть, содержащий сток. Как показывает теорема Форда — Фалкерсона, вес такого разреза равен максимальному потоку, который может быть пропущен из источника в сток через данную сеть.
• Разрез взвешенной неориентированной сети, который разделяет выделенную пару вершин и имеет минимальный вес. Система разрезов, которая решает задачу для любой пары вершин, может быть собрана в структуру, известную как дерево Гомори — Ху графа.

Граф с n вершинами может иметь не более ${\displaystyle n(n-1)/2}$ различных наименьших разрезов.

• Разрез (теория графов).
• Максимальный разрез графа, который содержит максимально возможное число рёбер
• Вершинный сепаратор, аналогичное понятие, но удаляются вершины, а не рёбра