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

Наименьший разрез графа — это минимальный в некотором смысле разрез (разбиение вершин графа на два непересекающихся множества, связанных по меньшей мере одним ребром).

Вариации

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

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

Число наименьших разрезов

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