Розмірність максимальних потоків

Розгляньмо ациклічний орієнтований граф $G$, у якому кожне ребро $uv$ має пропускну здатність $c(uv)$. Граф $G$ містить дві спеціальні вершини: витік $s$ і стік $t$.

Потоком у $G$ називається функція f : E \to R, яка задовольняє такі умови:

1. 0 \le f(uv) \le c(uv) для всіх ребер $uv$.

2. Для кожної вершини $u$, окрім $s$ і $t$, виконується:

Величина потоку $f$ позначається як $|f|$ і визначається як кількість потоку, що виходить з витоку:

Потік називається максимальним, якщо $|f|$ є найбільшим серед усіх можливих потоків у $G$. Можливо, існує кілька максимальних потоків.

Потоки можуть бути складені поточково або помножені на дійсну константу, як і будь-які інші функції. Зафіксуємо деякий максимальний потік f_{max}. Кажуть, що множина потоків \{f_1, f_2, \ldots, f_n\} утворює базис максимальних потоків, якщо кожен максимальний потік можна представити у вигляді суми

і жодна його підмножина не має цієї властивості. Тут a_i належить $R$.

Розмір цієї множини - $n$ - називається розмірністю максимальних потоків графа.

За заданим графом $G$ знайдіть розмірність його максимальних потоків.