Понятие разреза играет важную роль при изучении вопросов, связанных с отделением одного множества вершин графа от другого. Такие задачи возникают, например, при изучении потоков в сетях (сетью называется связный орграф G= потоком в сети G называется функция , которая ставит в соответствие дуги некоторое число- вес дуги). В этих задачах фундаментальную роль играют изучение поперечных сечений сети (т.е. множеств дуг, которые соединяют вершины двух непересекающихся множеств вершин) и нахождение ограниченного поперечного сечения, которое является самым узким местом. Эти узкие места определяют пропускную способность системы в целом.
Пусть G= - неорграф = разбиение множества M. Разрезом графа G (по разбиению ) называется множество всех ребер, соединяющих вершины из M1 с вершинами из M2 (рис. 4.46). Отметим, что в связном графе любой разрез непуст.
Непустой разрез K неорграфа G называется простым разрезом или коциклом, если любое непустое собственное подмножество K̕ K не является разрезом ни по какому разбиению. Другими словами, из K нельзя удалить ни одно ребро с тем,чтобы множество было непустым разрезом.
M₁ Разрез M₂