Лекції з дискретної математики - лекція 15
введемо позначення
V - вершина орграфа
M- (V) - безліч ребер, для яких вершина V є кінцем.
M + (V) - безліч ребер, для яких вершина V є початком.
Транспортною мережею називається зв'язний орграф без петель, для якого виконані наступні умови
1. Існує тільки одна вершина A, для якої M- (А) - порожня множина. А - витік.
2. Є тільки одна вершина B, для якої M + (B) - порожня множина. В - стік.
3. Кожному ребру графа поставлено у відповідність ціле невід'ємне число, зване пропускною спроможністю даного ребра.
Потоком в транспортній мережі (ТЗ) називається целочисленная функція, певна на будь-яких ребрах ТС і задовольняє таким властивостям
1. ф (X) 0 в новому графі g * замінюються двома ребрами x * і x **. Ребро x * направлено в ту ж сторону, що і x, і пропускна здатність c (x *) = c (x) - ф (x).
Ребро x ** направлено в протилежну сторону ребру x, і пропускна здатність c (x **) = ф (x).
Ребра з нульовою пропускною спроможністю можна не малювати.
3. У графі g * шукаємо шлях з А в В по ребрах з ненульовий пропускною спроможністю. Якщо його немає, то наявний потік є максимальним і алгоритм закінчений. Інакше переходимо до пункту 4.
(Цей шлях називається збільшеною ланцюгом. # 61508; # 61472; # 61501; # 61472; min (c (x)) - мінімальне значення пропускної здатності цього ланцюга).
4. Міняємо значення функції потоку в графі g для тих ребер, які відповідають знайденому шляху в графі перебудов за таким правилом:
Якщо напрямок ребра x в графі g збігається з напрямком шляху, то нове ф (x) = ф (x) + # 61508;
Якщо ж напрямок протилежно напрямку шляху, то ф (x) = ф (x) - # 61508;
5. Переходимо на крок 2 з новим потоком.