В теорії графів, потокова мережа (англ. flow network) це орієнтований граф де кожне ребро має ємність, пропускну спроможність і кожне ребро отримує потік. Загальний потік на ребрі не може перевищувати ємність ребра. В дослідженні операцій орієнтований граф часто називають мережею, вершини — вузлами і ребра — дугами. Потік має задовільняти обмеженю, що загальний вхідний потік вершини дорівнює загальному вихідному, за винятком джерела, що має більший вихідний потік, або стоку, що має більший вхідний потік. Таку мережу можна використати для моделювання руху в дорожній системі, струму в електронних мікросхемах або будь-чого, що рухається через мережу вузлів.
Визначення
скінченний орієнтований граф, в якому кожне ребро має додатню ємність . Якщо ми припускаємо, що . Ми розрізняємо дві вершини: джерело і стік . Потокова мережа — дійсна функція з наступними трьома властивостями для всіх вершин і :
Обмеження ємності (англ. capacity constraints): | . Потік уздовж ребра не може перевищити його ємність. |
Скісна симетрія (англ. skew symmetry): | . Потік мережі з до має бути протилежним до потоку з до (дивись приклад). |
Збереження потоку (англ. flow conservation): | , хіба що або . Мережевий потік у вершині нульовий, за винятком джерела, яке «виробляє» потік, і стоку, який «споживає» потік. |
Зауважте, що це мережевий потік з до . якщо граф представляє фізичну мережу і, якщо існує справжній потік, наприклад, в 4 одиниці з до , і справжній потік в 3 одиниці з до , тоді маємо і .
Залишкова ємність ребра це . Це визначає залишкову мережу позначувану , яка дає загальну доступну ємність. Може бути ребро з до в залишковій мережі, хоча не існує ребро з до в справжній мережі. Через те, що потоки в протилежних напрямках збалансовуються, зменшення потоку з до це те саме, що збільшення потоку з до . Шлях розширення це шлях в залишковій мережі, де , , і . Мережа перебуває в стані максимального потоку тоді і тільки тоді, коли не існує залишкового шляху в залишковій мережі.
Отже, створений із використанням графу таким чином:
- Вершини =
- Ребра = визначені так
Для кожного ребра
(i). Якщо утворити вперед-ребро з ємністю . (ii). Якщо утворити назад-ребро з ємністю .
Цю концепцію використовує алгоритм Форда — Фалкерсона, який обчислює максимальний потік у потоковій мережі.
Іноді необхідно змоделювати мережу з більше ніж одним джерелом, тоді вводять суперджерело. Воно утворене вершиною зв'язаною з кожним джерелом ребром нескінченної ємності, відтак діє як глобальне джерело. Подібна конструкція зветься суперстоком.
Див. також
Примітки
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V teoriyi grafiv potokova merezha angl flow network ce oriyentovanij graf de kozhne rebro maye yemnist propusknu spromozhnist i kozhne rebro otrimuye potik Zagalnij potik na rebri ne mozhe perevishuvati yemnist rebra V doslidzhenni operacij oriyentovanij graf chasto nazivayut merezheyu vershini vuzlami i rebra dugami Potik maye zadovilnyati obmezhenyu sho zagalnij vhidnij potik vershini dorivnyuye zagalnomu vihidnomu za vinyatkom dzherela sho maye bilshij vihidnij potik abo stoku sho maye bilshij vhidnij potik Taku merezhu mozhna vikoristati dlya modelyuvannya ruhu v dorozhnij sistemi strumu v elektronnih mikroshemah abo bud chogo sho ruhayetsya cherez merezhu vuzliv Viznachennya G V E displaystyle G V E skinchennij oriyentovanij graf v yakomu kozhne rebro u v E displaystyle u v in E maye dodatnyu yemnist c u v displaystyle c u v Yaksho u v E displaystyle u v not in E mi pripuskayemo sho c u v 0 displaystyle c u v 0 Mi rozriznyayemo dvi vershini dzherelo s displaystyle s i stik t displaystyle t Potokova merezha dijsna funkciya f V V R displaystyle f V times V rightarrow mathbb R z nastupnimi troma vlastivostyami dlya vsih vershin u displaystyle u i v displaystyle v Obmezhennya yemnosti angl capacity constraints f u v c u v displaystyle f u v leq c u v Potik uzdovzh rebra ne mozhe perevishiti jogo yemnist Skisna simetriya angl skew symmetry f u v f v u displaystyle f u v f v u Potik merezhi z u displaystyle u do v displaystyle v maye buti protilezhnim do potoku z v displaystyle v do u displaystyle u divis priklad Zberezhennya potoku angl flow conservation w Vf u w 0 displaystyle sum w in V f u w 0 hiba sho u s displaystyle u s abo w t displaystyle w t Merezhevij potik u vershini nulovij za vinyatkom dzherela yake viroblyaye potik i stoku yakij spozhivaye potik Zauvazhte sho f u v displaystyle f u v ce merezhevij potik z u displaystyle u do v displaystyle v yaksho graf predstavlyaye fizichnu merezhu i yaksho isnuye spravzhnij potik napriklad v 4 odinici z u displaystyle u do v displaystyle v i spravzhnij potik v 3 odinici z v displaystyle v do u displaystyle u todi mayemo f u v 1 displaystyle f u v 1 i f v u 1 displaystyle f v u 1 Zalishkova yemnist rebra ce cf u v c u v f u v displaystyle c f u v c u v f u v Ce viznachaye zalishkovu merezhu poznachuvanu Gf V Ef displaystyle G f V E f yaka daye zagalnu dostupnu yemnist Mozhe buti rebro z u displaystyle u do v displaystyle v v zalishkovij merezhi hocha ne isnuye rebro z u displaystyle u do v displaystyle v v spravzhnij merezhi Cherez te sho potoki v protilezhnih napryamkah zbalansovuyutsya zmenshennya potoku z v displaystyle v do u displaystyle u ce te same sho zbilshennya potoku z u displaystyle u do v displaystyle v Shlyah rozshirennya ce shlyah u1 u2 uk displaystyle u 1 u 2 dots u k v zalishkovij merezhi de u1 s displaystyle u 1 s uk t displaystyle u k t i cf ui ui 1 gt 0 displaystyle c f u i u i 1 gt 0 Merezha perebuvaye v stani maksimalnogo potoku todi i tilki todi koli ne isnuye zalishkovogo shlyahu v zalishkovij merezhi Otzhe Gf displaystyle G f stvorenij iz vikoristannyam grafu G displaystyle G takim chinom Vershini Gf displaystyle G f V displaystyle V Rebra Gf displaystyle G f Ef displaystyle E f viznacheni tak Dlya kozhnogo rebra x y E displaystyle x y in E i Yaksho f x y lt c x y displaystyle f x y lt c x y utvoriti vpered rebro x y Ef displaystyle x y in E f z yemnistyu cf c x y f x y displaystyle c f c x y f x y ii Yaksho f x y gt 0 displaystyle f x y gt 0 utvoriti nazad rebro y x Ef displaystyle y x in E f z yemnistyu cf f x y displaystyle c f f x y Cyu koncepciyu vikoristovuye algoritm Forda Falkersona yakij obchislyuye maksimalnij potik u potokovij merezhi Inodi neobhidno zmodelyuvati merezhu z bilshe nizh odnim dzherelom todi vvodyat superdzherelo Vono utvorene vershinoyu zv yazanoyu z kozhnim dzherelom rebrom neskinchennoyi yemnosti vidtak diye yak globalne dzherelo Podibna konstrukciya zvetsya superstokom Div takozhNide ne nulovij potikPrimitkiPol Blek Superdzherelo na NIST Pol Blek Superstik na NIST