Page 21 - 4517

7 8 3 9
1 3

5 2
1 5
2 3 9

2 6 7 10
2
4
4 7 4 6
1

3 5 7

Рисунок 5.1 – Граф досліджувальної мережі (варіант № 33)

Контрольні питання

1 Сформулюйте теорему про умови реалізації
максимальних потоків.
2 У чому полягає основна ідея стиснення декілька вузлів в
один вузол?
3 Які вузли мережі називають полюсами?
4 Як визначити величину максимального потоку між
довільними полюсами мережі?
5 З яких кроків складається алгоритм, який дає змогу за
заданою мережею побудувати еквівалентне дерево?

19