Разрез графа

Разре́з гра́фа в задачах о потоке — такая пара множеств вершин (S,T), что

1. $S \cup T=V$, где $V$ — множество вершин графа
2. $S\cap T=\emptyset$
3. $s \in S, t \in T$, где $s$ — исток, $t$ — сток.

Величиной разреза называется сумма пропускных способностей таких рёбер $(i, j)$, что $i \in S, j \in T$.

Другие определения разреза (сечения) графа

• Разрез графа — множество рёбер, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть отдельным узлом.
• Разрез графа — линия, делящая граф на две несвязанные части.

Характеристики

• Линии сечения могут пересекать произвольное число ребер и хорд.
• Для получения главного сечения графа нужно линию сечения графа провести таким образом, чтобы она пересекала только одну ветвь графа при произвольном пересечении хорд.

См. также

• Граф (математика)
• Поток в графе
• Теорема Форда — Фалкерсона