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

В теорії графів, потокова мережа (англ. 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)\leq 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$ . Мережа перебуває в стані максимального потоку тоді і тільки тоді, коли не існує залишкового шляху в залишковій мережі.

Отже, $\ G_{f}$ створений із використанням графу $G$ таким чином:

Вершини $\ G_{f}$ = $\ V$
Ребра $\ G_{f}$ = $\ E_{f}$ визначені так

Для кожного ребра $\ (x,y)\in E$

    (i). Якщо  $\ f(x,y)<c(x,y),$  утворити вперед-ребро  $\ (x,y)\in E_{f}$  з ємністю  $\ c_{f}=c(x,y)-f(x,y)$ .
    (ii). Якщо  $\ f(x,y)>0,$  утворити назад-ребро  $\ (y,x)\in E_{f}$  з ємністю  $\ c_{f}=f(x,y)$ .

Цю концепцію використовує алгоритм Форда — Фалкерсона, який обчислює максимальний потік у потоковій мережі.

Іноді необхідно змоделювати мережу з більше ніж одним джерелом, тоді вводять суперджерело.^[1] Воно утворене вершиною зв'язаною з кожним джерелом ребром нескінченної ємності, відтак діє як глобальне джерело. Подібна конструкція зветься суперстоком.^[2]

Див. також

Ніде не нульовий потік

Примітки

↑ Пол Блек, Суперджерело на NIST Словник алгоритмів і структур даних.
↑ Пол Блек, Суперстік на NIST Словник алгоритмів і структур даних.

[1] Пол Блек, Суперджерело на NIST Словник алгоритмів і структур даних.

[2] Пол Блек, Суперстік на NIST Словник алгоритмів і структур даних.

[1]

[2]