Page 95 - 2589

 0    (u )    (u )   c (u )  0  c (V ). (4.12)
z
  
u U V u U V u U V
0
Згідно з доведеною лемою 4.1,  є найбільшим потоком, а
z
V — переріз з найменшою пропускною здатністю.

Приклад 4.8: Розмітка індексів вершин транспортної мережі
приведена на рис.4.9,а. Вершина z виявилась позначеною
4
індексом  . Спадаюча послідовність індексів  , 4  , 3  , 2  0
визначає ланцюг   (x ,x ,x ,x , ) z , потік в якому від x до z
0 2 3 4 0
потрібно збільшити на одиницю. Це приводить до розподілу
потоку, показаному на рис.4.9,б. Повторюючи процес розмітки
індексів на цьому рисунку, знаходимо ланцюг

  (x ,x ,x x ,x , ) z , потік в який також повинен бути
0 2 1 3 4
збільшений на одиницю. Результуючий розподіл потоку показано
на рис.4.9,в. При розмітці індексів на цьому рисунку
залишаються непозначеними вершини x і z.
4
Отже, отриманий розподіл потоку забезпечує найбільший
0
потік  в розглянутій транспортній мережі, а множина
z
 z
V  x , визначає переріз з найменшою пропускною здатністю.
4
0
Величину потоку  знайдемо, визначивши пропускну здатність
z
перерізу V :
 0  c (x ,x )  c (x ,x )  c (x ,z )  3  1 2  6.
z 2 4 3 4 3
Збільшити найбільший потік транспортної мережі можливо

шляхом збільшення пропускної здатності будь-якої з дуг, що
заходять в переріз V .

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

1. Що таке граф, ребро, дуга, порядок графа?
2. Що таке орієнтований граф, мішаний граф, мультиграф,
псевдограф?
3. Що таке локальні степені вершин орієнтованого графа?

4. Що таке частина графа, суграф та підграф?
5. Що таке маршрут, ланцюг і цикл графа?
6. Як формулюються еквівалентні означення дерева графа?

8. Що таке хроматичне число графа?
11. Що таке планарний граф?
13. Як формулюється екстремальна задача в теорії графів?
14. Що таке компонента зв'язності?

95