Потокова мережа — Вікіпедія

Наука про мережі
Теорія
Граф Складні мережі Світ тісний Безмасштабна мережа Перколяція Структура спільноти Еволюція[en] Керованість[en] Візуалізація графів Соціальний капітал Аналіз зв’язків Оптимізація Транзитивність Теорія балансу Ефект мережі Соціальний вплив
Види мереж
Інформаційна (комп'ютерна) Телекомунікаційна Транспортна Соціальна аналіз Біологічна[en] Штучна нейронна мережа Семантична Просторова Залежностей[en] Потокова
Графи
Властивості Кліка Компонент Розріз Цикл Структура даних Ребро Петля Окіл Шлях Вершина Список суміжності[en] / матриця Список інцидентності / матриця Види Двочастковий Повний Орієнтований Гіперграф Мультиграф Випадковий Зважений
Метрики[en] Алгоритми
Центральність Степінь Близькість[ru] PageRank Кластеризація Асортативність[en] Відстань Модулярність[en] Ефективність[en]
Моделі
Топологія Випадковий граф Модель Ердеша — Реньї Модель Барабаші — Альберт Модель Воттса — Строгаца Гіперболічна (HGN)[en] Ієрархічна[en] Стохастична блокова модель Динаміка Булева мережа Агентне моделювання Епідемічні/SIR
Списки Категорії
Категорія:Теорія мереж Категорія:Теорія графів
п о р

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

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

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

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

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

Залишкова ємність ребра це ${\displaystyle \ c_{f}(u,v)=c(u,v)-f(u,v)}$. Це визначає залишкову мережу позначувану ${\displaystyle \ G_{f}(V,E_{f})}$, яка дає загальну доступну ємність. Може бути ребро з ${\displaystyle \ u}$ до ${\displaystyle \ v}$ в залишковій мережі, хоча не існує ребро з ${\displaystyle \ u}$ до ${\displaystyle \ v}$ в справжній мережі. Через те, що потоки в протилежних напрямках збалансовуються, зменшення потоку з ${\displaystyle \ v}$ до ${\displaystyle \ u}$ це те саме, що збільшення потоку з ${\displaystyle \ u}$ до ${\displaystyle \ v}$. Шлях розширення це шлях ${\displaystyle \ (u_{1},u_{2},\dots ,u_{k})}$ в залишковій мережі, де ${\displaystyle \ u_{1}=s}$, ${\displaystyle \ u_{k}=t}$, і ${\displaystyle \ c_{f}(u_{i},u_{i+1})>0}$. Мережа перебуває в стані максимального потоку тоді і тільки тоді, коли не існує залишкового шляху в залишковій мережі.

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

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

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

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

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

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

Див. також[ред. | ред. код]

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

Примітки[ред. | ред. код]