На головну

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

  1. Аудіо-потоки в Windows XP аудіо-потоки в Windows 7 і Vista
  2. Біологічні принципи управління. Поняття про штучні нейронних мережах.
  3. В інтер І ІНТРА-МЕРЕЖАХ
  4. Взаємодія людини з середовищем проживання може бути позитивним або негативним, характер взаємодії визначають потоки речовини, енергії та інформації.
  5. Грошові потоки
  6. Грошові потоки інвестиційного проекту
  7. Інформаційні потоки

Терезам дуг можна дати іншу інтерпретацію, в результаті виникає цікава і важлива задача. Нехай в орієнтованому зваженому графі виділені дві вершини (b - Початкова і e - кінцева). Передбачається, що вершина e досяжна з b. Змістовний сенс ваг дуг це пропускна здатність доріг. Нас цікавлять перевезення з вершини b в вершину e. Природним є питання: який максимальний вантаж можна перевезти з початкової вершини в кінцеву? На відміну від відстаней вага вантажу, що перевозиться по ланцюгу, що не дорівнює сумі ваг вантажів, що перевозяться по окремим дуг. Поставлену задачу називають задачею про максимальний потік. Слово «потік» тут є природним, оскільки можна говорити про потік вантажів, можна задачу інтерпретувати і як аналіз потоків рідини в трубопроводах. Наведемо формальне визначення. Позначення г (v), Г-1(v) Мають таке ж значення, що і в попередньому параграфі.

ВИЗНАЧЕННЯ 35.Потоком в сетіот вершини b до вершини e називається певна на дугах графа неотрицательная числова функція x (u, v), Що задовольняє умовам:

x (u, v) ? c(u, v);

 при u?b, e;

.

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

З поняттям потоку тісно пов'язане поняття розрізу.

ВИЗНАЧЕННЯ 36.розрізомв графі Г, що розділяє початкову і кінцеву вершини, називається сімейство дуг, після видалення яких у відповідному неориентированном графі початкова і кінцева вершини належать різним компонентам зв'язності (назвемо їх b-компонента і e-компонента).

Образно кажучи, розріз це стіна, яка відділяє кінцеву вершину від початкової. Зрозуміло, при додаванні дуг до розрізу також отримуємо розріз.

величиною розрізу називається сума ваг дуг в розрізі, провідних фахівців із b-компоненти і e-компонента. Попереднє зауваження говорить про те, що має сенс говорити про мінімальному розрізі, розділяє початкову і кінцеву вершини, як про розрізі з мінімальною величиною.

теорема 27(Форда-Фалкерсона). При заданих початковій і кінцевій вершинах мережі величина максимального потоку дорівнює величині мінімального розрізу.

Доведення. Перш за все, величина будь-якого потоку не перевищує величини будь-якого розрізу. Дійсно, з b в e не можна перевезти вантажу більше, ніж через стіну, що відокремлює b від e. Таким чином, якщо ми знайдемо потік і розріз з рівними величинами, то це неодмінно максимальний потік і мінімальний розріз.

Побудова фактично є алгоритмом побудови максимального потоку і мінімального розрізу, ефективним при цілих вагах дуг.

При побудові важливу роль відіграє наступна конструкція. Розглянемо послідовність вершин і дуг, що з'єднують b и e, причому напрямки дуг можуть бути різними. Дуги, спрямовані від b к e, назвемо прямими, в протилежному напрямку - зворотними. (Відзначимо, що дуга, яка є прямою в одного ланцюга, може бути зворотною в інший). Така послідовність називається збільшує ланцюгом з b в e, Якщо для прямих дуг x (u, v) <c(u, v), А для зворотних x (u, v)> 0. нехай p= Min {c(u, v) -x (u, v)} Для прямих дуг, q =min {x (u, v)} Для зворотних дуг ланцюга, r= Min {p, q}> 0. потік з b в e можна збільшити за збільшує ланцюга на величину r, поклавши x (u, v): = X (u, v) +r на прямих дугах і x (u, v): = X (u, v) -r на зворотних. Отримані значення також є потоком (перевірте це!). Після такого перетворення ланцюг не є збільшує, оскільки для деякої прямої дуги x (u, v) =c(u, v) Або (НЕ розділову) для деякої зворотного - x (u, v) = 0.

Побудова потоку з потрібними властивостями полягає в послідовному видаленні за допомогою описаної конструкції збільшують ланцюгів і таким чином в збільшенні потоку з b в e, Поки це можливо. На початку потік приймається нульовим. Оскільки при кожній ітерації потікзбільшується як мінімум на 1 (ваги дуг цілі!), А величина потоку обмежена зверху (наприклад, сумою ваг всіх дуг графа), то після кінцевого числа ітерацій збільшують ланцюгів в графі не буде. Отриманий потік збільшити не можна (якщо б це можна було зробити, то відповідна ланцюг була б збільшує), т. Е. Він максимальний.

Розіб'ємо безліч вершин V на два класи. В перший (V1) Входять такі вершини v, Для яких існує збільшує ланцюг з b в v, у другий (V2) - Інші вершини. Обидва класи непусті: bIV1, eIV2, Т. Е. Це b и e-компоненти. Дуги, спрямовані з V1 в V2 і навпаки, утворюють розріз. При цьому якщо (u, v) Дуга, uIV1, vIV2, То x =c(u, v). Дійсно, в іншому випадку (т. Е. При x (u, v) <c(u, v)), Приєднавши до збільшує ланцюга з b в u дугу (u, v), Отримаємо збільшує ланцюг з b в v, що неможливо з побудови. Аналогічно, якщо uIV2, vIV1, То x (u, v) = 0.

Величина побудованого розрізу дорівнює сумі ваг «прямих» дуг. Доведемо, що величина побудованого максимального потоку дорівнює сумі ваг тих же дуг. Кожна одиниця вантажу доставляється з якої-небудь з цих дуг, причому по єдиною. Якби таких дуг було більше однієї, то ця одиниця вантажу доставлялася б за деякою дузі, що веде з V2 в V1, А на цих дугах потік нульовий. Теорема Форда-Фалкерсона доведена.

Ідея алгоритму, описаного при доведенні теореми, реалізується формуванням позначок вершин тим чи іншим чином. Основний недолік цього підходу полягає в тому, що немає ніяких вказівок щодо побудови збільшують ланцюгів, а від їх вибору сильно залежить число ітерацій. У другій половині 20 століття розроблено безліч більш простих алгоритмів побудови максимального потоку.

Питання для самоперевірки

1. Що таке граф? З чого він складається? Які види графів ви знаєте?

2. Які вершини, дуги називаються суміжними? Інцидентними?

3. Які графи називаються ізоморфними?

4. Що таке підграф? Які види подграфов ви знаєте?

5. Що таке ступінь вершини? Полустепені входу і виходу?

6. Чому дорівнює сума ступенів вершин графа?

7. Які графи називаються суміжних і додаткових до даного?

8. Як будуються матриці суміжності і інціденцій графа?

9. Що таке маршрут, ланцюг, цикл, простий ланцюг, простий цикл?

10. Які вершини називаються досяжними? Взаємно досяжними?

11. Що таке компонента сильної зв'язності (зв'язності)?

12. Як будується матриця досяжності?

13. Як визначається зважений граф?

14. Що таке ліс? Дерево?

15. Якими властивостями володіють дерева?

16. Скільки існує неізоморфних помічених дерев з даними числом вершин?

17. Що таке радіус, діаметр, центр графа?

18. Як влаштований центр дерева?

19. Що таке мінімальне кістяк зваженого графа?

20. Що таке Ейлером цикл, Ейлером шлях, Ейлером граф, полуейлеров граф?

21. Який критерій ейлерову графа?

22. Що таке гамильтонов цикл, гамільтонів шлях, гамільтонів граф, полугамільтонов граф?

23. Як формулюється теорема Дірака?

24. Як формулюється задача комівояжера?

25. У чому ідея методів пошуку з поверненням та гілок і меж?

26. Що таке Графова вектор?

27. Як перевірити, що вектор є графову?

28. Як влаштований Графова вектор дерева?

29. Що таке паросочетание? Максимальна паросочетание?

30. Що таке реберне покриття? Мінімальна реберне покриття?

31. Як пов'язані максимальне паросполучення і мінімальне реберне покриття

32. Що таке повне паросочетание в дводольному графі?

33. Який критерій існування повного паросполучення в дводольному графі?

34. Що таке правильна нумерація вершин і в яких графах вона існує?

35. Що таке мережевий графік?

36. Які шляхи в мережевому графіку називаються критичними?

37. Що таке потік в мережі? Розріз мережі?

38. Як пов'язані максимальний потік і мінімальний розріз?

 



Мережеві графіки | вправи

Вступ | Розміщення без повторень | Сполучення (без повторень) | Властивості біноміальних коефіцієнтів | розбиття множин | Сполучення з повтореннями | різні завдання | виробляють функції | Використання рекурентних співвідношень | Формула включень та виключень |

© um.co.ua - учбові матеріали та реферати