WikiSort.ru - Не сортированное

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

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

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

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

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

См. также

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