Потокова мережа

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

В теорії графів, потокова мережа (англ. flow network) це орієнтований граф де кожне ребро має ємність, пропускну спроможність і кожне ребро отримує потік. Загальний потік на ребрі не може перевищувати ємність ребра. В дослідженні операцій орієнтований граф часто називають мережею, вершини — вузлами і ребра — дугами. Потік має задовільняти обмеженю, що загальний вхідний потік вершини дорівнює загальному вихідному, за винятком джерела, що має більший вихідний потік, або стоку, що має більший вхідний потік. Таку мережу можна використати для моделювання руху в дорожній системі, струму в електронних мікросхемах або будь-чого, що рухається через мережу вузлів.

Визначення[ред.ред. код]

\ G(V,E) скінченний орієнтований граф, в якому кожне ребро \ (u,v) \in E має додатню ємність \ c(u,v). Якщо \ (u, v) \not \in E ми припускаємо, що \ c(u, v) = 0. Ми розрізняємо дві вершини: джерело \ s і стік \ t. Потокова мережа — дійсна функція \ f:V \times V \rightarrow \mathbb{R} з наступними трьома властивостями для всіх вершин \ u і \ v:

Обмеження ємності (англ. capacity constraints): \ f(u,v) \le c(u,v). Потік уздовж ребра не може перевищити його ємність.
Скісна симетрія (англ. skew symmetry): \ f(u,v) = - f(v,u). Потік мережі з \ u до \ v має бути протилежним до потоку з \ v до \ u (дивись приклад).
Збереження потоку (англ. flow conservation): \ \sum_{w \in V} f(u,w) = 0, хіба що \ u=s або \ w=t. Мережевий потік у вершині нульовий, за винятком джерела, яке «виробляє» потік, і стоку, який «споживає» потік.

Зауважте, що \ f(u,v) це мережевий потік з \ u до \ v. якщо граф представляє фізичну мережу і, якщо існує спраіжній потік, наприклад, в 4 одиниці з \ u до \ v, і справжній потік в 3 одиниці з \ v до \ u, тоді маємо \ f(u,v)=1 і \ f(v,u)=-1.

Залишкова ємність ребра це \ c_f(u,v) = c(u,v) - f(u,v). Це визначає залишкову мережу позначувану \ G_f(V,E_f), яка дає загальну доступну ємність. Може бути ребро з \ u до \ v в залишковій мережі, хоча не існує ребро з \ u до \ v в справжній мережі. Через те, що потоки в протилежних напрямках збалансовуються, зменшення потоку з \ v до \ u це те саме, що збільшення потоку з \ u до \ v. Розширений шлях, залишковий шлях це шлях \ (u_1,u_2,\dots,u_k) в залишковій мережі, де \ u_1=s, \ u_k=t, і \ c_f(u_i, u_{i+1}) > 0. Мережа перебуває в стані максимального потоку тоді і тільки тоді, коли не існує залишкового шляху в залишковій мережі.