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