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

Введемо розбиття вершин графа на дві неперетинні множини, тоді розріз графа складає множина дуг, які з’єднують утворені підмножини вершин.

В потоковій мережі, s-t розріз це розріз, в якому джерело (англ. source) і стік (англ. sink), вершини з нульовими напівстепенями входу і виходу відповідно, знаходяться в різних підмножинах вершин, та містить лише дуги, що ведуть від джерела до стоку. Сума пропускних здатностей усіх дуг розрізу називається величиною розрізу (його пропускною здатністю).

Також розрізом графа можуть називати дві утворені множини вершин.

Найменший розріз

Розріз є найменшим, якщо розмір розрізу не більший ніж розмір будь-якого іншого розрізу. Зображення праворуч показує найменший розріз: розмір розрізу дорівнює 2, і не існує розрізу з розміром 1, бо граф без мостів.

Теорема Форда — Фалкерсона доводить, що найбільший мережевий потік і сума ваг ребер будь-якого найменшого розрізу, що розділяє джерело і стік однакові. Існують методи з поліноміальним часом для розв'язання задачі найменшого розрізу, досить відомий алгоритм Едмондса-Карпа.

Найбільший розріз

Найбільший розріз

Розріз називається найбільшим, якщо його розмір не менше розміру будь-якого іншого розрізу. Зображення праворуч показує найбільший розмір: розмір розрізу складає |E|  = 5, і не існує розрізу більшого розміру бо граф не двочастковий (присутній непарний цикл).

Загалом, знаходження найбільшого розрізу складно для обчислення. Задача найбільшого розрізу це одна з 21 NP-повної задачі Карпа. Задача найбільшого розрізу також є APX-складною, тобто не існує схеми наближення до поліноміального часу, хіба що P = NP.

Зауважте, що задачі найменшого і найбільшого розрізів не двоїсті в сенсі лінійного програмування, попри те, що одну можна отримати з іншої замінив найбільший на найменший в цільовій функції. Двоїстою до задачі найменшого розрізу є задача про найбільший потік.

Див. також

• Зв'язний граф
• Алгоритм Прима
• Провідність графа