Розріз (теорія графів)
Введемо розбиття вершин графу на дві неперетинні множини, тоді розріз графу складає множина дуг, які з’єднують утворені підмножини вершин.
В потоковій мережі, s-t розріз це розріз, в якому джерело (англ. source) і стік (англ. sink), вершини з нульовими напівстепенями входу і виходу відповідно, знаходяться в різних підмножинах вершин, та містить лише дуги, що ведуть від джерела до стоку. Сума пропускних здатностей усіх дуг розрізу називається величиною розрізу (його пропускною здатністю).
Також розрізом графу можуть називати дві утворені множини вершин.
Найменший розріз
Розріз є найменшим, якщо розмір розрізу не більший ніж розмір будь-якого іншого розрізу. Зображення праворуч показує найменший розріз: розмір розрізу дорівнює 2, і не існує розрізу з розміром 1, бо граф без мостів.
теорема Форда—Фалкерсона доводить, що найбільший мережевий потік і сума ваг ребер будь-якого найменшого розрізу, що розділяє джерело і стік однакові. Існують методи з поліноміальним часом для ров'язання задачі найменшого розрізу, досить відомий алгоритм Едмондса-Карпа.
Найбільший розріз
Розріз називається найбільшим, якщо його розмір не менше розміру будь-якого іншого розрізу. Зображення праворуч показує найбільший розмір: розмфр розрізу складає |E| = 5, і не існує розрізу більшого розміру бо граф не дводольний (присутній непарний цикл).
Загалом, знаходження найбільшого розрізу складно для обчислення. Задача найбільшого розрізу це одна з 21 NP-повної задачі Карпа. Задача найбільшого розрізу також є APX-складною, тобто не існує схеми наближення до поліноміального часу, хіба що P = NP.
Зауважте, що задачі найменшого і найбільшого розрізів не двоїсті в сенсі лінійного програмування, попри те, що одну можна отримати з іншої замінив найбільший на найменший в цільовій функції. Двоїстою до задачі найменшого розрізу є задача про найбільший потік.