Разрез (теория графов)

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

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

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

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

Разрез графа

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

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

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

См. также

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