Page 79 - 4496

множину Y. Позначки вершин здійснюються від джерела.
Кожна позначка вершини (якщо ця вершина може бути
позначена) складається із двох чисел: перше - це “+” або “-”
номер вершини (з Y), з якої зв'язана нова позначувана
вершина, і друге - (обов'язково повинне бути позитивним) - це
фактично та добавка до потоку, що може бути додатково
“довезена” у цю вершину із джерела в порівнянні з вихідним
потоком.
Більш точно, множина позначених вершин Y утвориться
в такий спосіб:
джерело t належить Y і його позначка (0, ); друге
число, умовно говорячи, дорівнює нескінченності – що для
дискретної математики означає, що це настільки велике число,
як нам знадобиться;
якщо вершина належить Y і c ij < qij (дуга (i,j) – пряма й
ненасичена), то вершина j також належить Y і позначка
вершини j дорівнює (+i, j), де j>0 дорівнює j= min {i, q ij –
c ij}. Помітимо, що тут число  i – це друге число вже
позначеної вершини i, а знак + перед номером i означає, що
дуга, що зв'язує вершини (i, j) є прямій (і ненасиченої);
якщо вершина до належить Y і с jk > 0 (зворотна дуга), то
вершина з номером j також повинна належати Y й її позначка
дорівнює (– до,  j), де знак мінус означає, що вершина j
пов'язана із уже позначеною вершиною до зворотною дугою,
 j= min{ k, q jk+c jk}, причому очевидно, що  j також строго
більше нуля. Таким чином, побудова множини Y є
індуктивним, тобто нова вершина додається в Y, якщо вона
пов'язана з деякою вершиною вже вхідної в Y або прямій
ненасиченою дугою, або зворотною дугою.
Після того як побудова множини Y закінчена (до нього
не можна додати нових вершин), можливі 2 випадки.
1 Стік (тобто вершина з номером s) не входить у
множину вершин Y. Тоді позначимо множину вершин, що не
входять в Y через Z. Наш граф за умовою є зв'язковим, тому з
Y, в Z ідуть деякі ребра. За правилами побудови Y всі ці ребра
є прямими насиченими дугами (рис. 3.13).
Ребра, що йдуть із множини Y в Z, утворять перетин між
вершинами t й s. Видно також, що сума пропускних
здатностей ребер цього перетину (а всі ці ребра є прямими,
насиченими) дорівнює потоку з t у s. Виходить, даний потік є
76