7.составім рекурентне співвідношення:
складемо характеристичне рівняння:
маємо коріння
за формулами знаходь спільне рішення:
, де
отримаємо
. Побудуємо по матриці ваг граф.
Рис.
Потім виберемо початковою вершиною вершину В, і розслабимо сусідні вершини D і E.
Рис.
Потім, вибираємо найменшу вершину, тобто Е, і продовжуємо виконання алгоритму пошуку мінімального покриває дерева.
Рис.
Рис.
Рис.
Рис.
. Побудуємо дерево найкоротших відстаней з вершини V 0, використовуючи алгоритм Дейкстри
Рис.
величина завдання дискретний математика
Рис.
Маршрут V 0, V 3, V 4, V 1, V 2, V 5 є найкоротшим, тому його довжина дорівнює 5, у той час як довжина маршрутів V 0, V 5; V 0, V 3, V 4, V 5; V 0, V 1, V 2, V 5; V 0, V 3, V 2, V 5 дорівнює 6.
. Знайдемо величину максимального потоку в мережі, використовуючи алгоритм Форда - Фалкерсона.
Рис.
Для початку заповнимо всі потоки так:
Рис.
І так:
Рис.
У результаті ми маємо повністю заповнену мережу, де пропускна здатність Інкремент вершині Т дуг повністю витрачена, і значить більше пропустити через цю вершину вже неможливо.
Рис.
Таким чином величина максимального потоку в мережі дорівнює сумі величин потоків на дугах інкрементних вихідний вершині Т, тобто дорівнює 6.
Якщо провести перевірку, то ми побачимо, що в кожну вершину скільки потоків увійшло, стільки ж і вийшло, як і у всій мережі в цілому: увійшло шість і вийшло шість.
Моя думка про це прикладі таке, що він не вдалий для демонстрації роботи алгоритму, оскільки вся мережа заповнюється всього за один підхід, і подальші обчислення, які є суть алгоритму, стають зайвими.
3.
