Перегляд вихідного коду сторінки Потокова мережа

У Вас нема дозволу на редагування цієї сторінки з такої причини:

Ваша IP-адреса знаходиться в діапазоні, який заблоковано у всіх вікі Фонду Вікімедіа.

Блокування зроблено ‪EPIC‬. Причиною вказано Open proxy/Webhost: See the help page if you are affected.

Початок блокування: 08:48, 2 липня 2024
Закінчення блокування: 08:48, 2 липня 2025

Ваша поточна IP-адреса: 206.189.44.186. Заблокований діапазон — 206.189.32.0/20.

Будь ласка, додайте всі вказані подробиці до будь-яких запитів, які Ви будете робити. Якщо ви вважаєте, що вас заблокували помилково, ви можете знайти додаткову інформацію та інструкції в глобальній політиці Без відкритих проксі.

В іншому випадку, щоб обговорити блокування, будь ласка, опублікуйте запит на розгляд на Мета-вікі. Ви також можете надіслати електронний лист до VRT-черги стюардів за адресою stewards@wikimedia.org, вказавши усю вищезазначену інформацію.

Ви можете переглянути та скопіювати вихідний текст цієї сторінки:

{{Наука про мережі}}
В [[теорія графів|теорії графів]], '''потокова мережа''' ({{lang-en|flow network}}) це [[орієнтований граф]] де кожне ребро має '''ємність''', '''пропускну спроможність''' і кожне ребро отримує потік. Загальний потік на ребрі не може перевищувати ємність ребра. В [[Дослідження операцій|дослідженні операцій]] орієнтований граф часто називають '''мережею''', вершини&nbsp;— '''вузлами''' і ребра&nbsp;— '''дугами'''. Потік має задовільняти обмеженю, що загальний вхідний потік вершини дорівнює загальному вихідному, за винятком '''джерела''', що має більший вихідний потік, або '''стоку''', що має більший вхідний потік. Таку мережу можна використати для моделювання руху в дорожній системі, струму в електронних мікросхемах або будь-чого, що рухається через мережу вузлів.

==Визначення==

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

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

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

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

Отже, <math>\ G_f</math> створений із використанням графу <math>G</math> таким чином:

# Вершини <math>\ G_f</math> = <math>\ V </math>
# Ребра <math>\ G_f</math> = <math>\ E_f</math> визначені так

Для кожного ребра <math>\ (x,y) \in E </math> 
     (i). Якщо <math>\ f(x,y) < c(x,y), </math> утворити вперед-ребро <math>\ (x,y) \in E_f</math> з '''ємністю''' <math>\ c_f = c(x,y) - f(x,y) </math>.
     (ii). Якщо <math>\ f(x,y) > 0, </math> утворити назад-ребро <math>\ (y, x) \in E_f</math> з '''ємністю''' <math>\ c_f =  f(x,y) </math>.

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

Іноді необхідно змоделювати мережу з більше ніж одним джерелом, тоді вводять '''суперджерело'''.<ref>{{DADS|Суперджерело|supersource}}</ref> Воно утворене вершиною зв'язаною з кожним джерелом ребром нескінченної ємності, відтак діє як глобальне джерело. Подібна конструкція зветься '''суперстоком'''.<ref>{{DADS|Суперстік|supersink}}</ref>

== Див. також ==
* [[Ніде не нульовий потік]]

== Примітки ==
{{reflist}}
{{Алгоритми на графах}}
[[Категорія:Мережевий потік]]
[[Категорія:Алгоритми на графах]]
[[Категорія:Дослідження операцій]]

Шаблони, використані на цій сторінці:

Шаблон:CSS image crop (переглянути вихідний код) (частково захищено)
Шаблон:Cl (переглянути вихідний код) (частково захищено)
Шаблон:DADS (редагувати)
Шаблон:Hlist (переглянути вихідний код) (частково захищено)
Шаблон:Hlist/styles.css (переглянути вихідний код) (захищено)
Шаблон:Ifnumber (переглянути вихідний код) (частково захищено)
Шаблон:Lang-en (переглянути вихідний код) (захищено)
Шаблон:Main other (переглянути вихідний код) (захищено)
Шаблон:Navbox (переглянути вихідний код) (захищено)
Шаблон:Nobr (переглянути вихідний код) (захищено)
Шаблон:Nowrap (переглянути вихідний код) (захищено)
Шаблон:Reflist (переглянути вихідний код) (захищено)
Шаблон:Reflist/styles.css (переглянути вихідний код) (захищено)
Шаблон:Sidebar (переглянути вихідний код) (частково захищено)
Шаблон:Subinfobox bodystyle (редагувати)
Шаблон:Subsidebar bodystyle (редагувати)
Шаблон:Yesno (переглянути вихідний код) (захищено)
Шаблон:\ (переглянути вихідний код) (частково захищено)
Шаблон:Алгоритми на графах (редагувати)
Шаблон:Наука про мережі (редагувати)
Шаблон:Не перекладено (переглянути вихідний код) (захищено)
Шаблон:Нп (переглянути вихідний код) (захищено)
Шаблон:Якір (переглянути вихідний код) (захищено)
Шаблон:Якірець (редагувати)
Модуль:Arguments (переглянути вихідний код) (захищено)
Модуль:Check for unknown parameters (переглянути вихідний код) (захищено)
Модуль:Lang (переглянути вихідний код) (захищено)
Модуль:Lang/ISO 639 synonyms (переглянути вихідний код) (захищено)
Модуль:Lang/data (переглянути вихідний код) (захищено)
Модуль:Lang/data/iana languages (переглянути вихідний код) (захищено)
Модуль:Lang/data/iana regions (переглянути вихідний код) (захищено)
Модуль:Lang/data/iana scripts (переглянути вихідний код) (захищено)
Модуль:Lang/data/iana suppressed scripts (переглянути вихідний код) (захищено)
Модуль:Lang/data/iana variants (переглянути вихідний код) (захищено)
Модуль:Lang/data/languages abbr. (переглянути вихідний код) (захищено)
Модуль:List (переглянути вихідний код) (захищено)
Модуль:Navbar (переглянути вихідний код) (захищено)
Модуль:Navbar/configuration (переглянути вихідний код) (захищено)
Модуль:Navbar/styles.css (переглянути вихідний код) (захищено)
Модуль:Navbox (переглянути вихідний код) (захищено)
Модуль:Navbox/configuration (переглянути вихідний код) (захищено)
Модуль:Navbox/styles.css (переглянути вихідний код) (захищено)
Модуль:Sidebar (переглянути вихідний код) (частково захищено)
Модуль:Sidebar/configuration (переглянути вихідний код) (частково захищено)
Модуль:Sidebar/styles.css (переглянути вихідний код) (частково захищено)
Модуль:TableTools (переглянути вихідний код) (захищено)
Модуль:Unicode data (переглянути вихідний код) (захищено)
Модуль:Unicode data/scripts (переглянути вихідний код) (захищено)
Модуль:Yesno (переглянути вихідний код) (захищено)
Модуль:Не перекладено (переглянути вихідний код) (захищено)
Модуль:Якір (переглянути вихідний код) (захищено)

Повернення до сторінки «Потокова мережа».

Отримано з https://uk.wikipedia.org/wiki/Потокова_мережа