Разре́з гра́фа в задачах о потоке — такая пара множеств вершин (S,T), что
, где — множество вершин графа
, где — исток, — сток.
Величиной разреза называется сумма пропускных способностей таких рёбер , что .
Другие определения разреза (сечения) графа
Разрез графа — множество рёбер, образующих двудольный подграф, удаление которых делит граф на две или более компоненты, которые, в частности, могут быть изолированными узлами. А также линия, проходящая через все рёбра разреза графа.
Характеристики Линии сечения могут пересекать произвольное число рёбер и хорд. Для получения главного сечения графа нужно линию сечения графа провести таким образом, чтобы она пересекала только одну ветвь графа при произвольном пересечении хорд.
См. также Наименьший разрез Граф (математика) Поток в графе Теорема Форда — Фалкерсона
Категория:Теория графов Категория:Связность графа