Остаточный граф

Для заданной потоковой сети G и потокаf в G остаточный граф Gf для G в отноше- нии f определяется следующим образом (остаточный граф потока на рис. 7.3 после проталкивания 20 единиц потока по пути s, u, v, t изображен на рис.
7.4):

♦ Множество узлов Gf совпадает с множеством узлов G.

♦ Для каждого ребра e = (u, v) графа G, для которого f (e) < с, имеются ce - f (e) «резервных» единиц пропускной способности, на которые можно попытаться нарастить поток.

Рис. 7.4. (a) Граф G с путем s, u, v, t используется для проталкивания первых 20 единиц потока. (b) Остаточный граф полученного потокаf рядом с каждым ребром обозначена остаточная пропускная способность. Пунктирная линия обозначает новый увеличивающий путь.

(с) Остаточный граф после проталкивания дополнительных 10 единиц потока по новому увеличивающему пути s, u, v, t


Соответственно в g/ включается ребро e = (u, v) с пропускной способностью ce - f (e). Ребра, включаемые таким образом, называются прямыми ребрами.

♦ Для каждого ребра e = (u, v) графа G, для которого f(e) > 0, имеются f(e) еди- ниц потока, которые можно при необходимости «отменить», направив поток в обратном направлении. Соответственно в g/ включается ребро e' = (v, u) с пропускной способностьюf (e). Заметьте, что e' имеет те же концы, что и e, но проходит в обратном направлении; ребра, включаемые таким образом, называ- ются обратными ребрами.

На этом определение остаточного графа g/ можно считать завершенным. Об- ратите внимание: каждое ребро e в G может породить одно или два ребра в Gf: если 0 < f (e) < ce, в Gf включается как прямое, так и обратное ребро. Следовательно, количество ребер в Gf может быть до двух раз больше, чем количество ребер в G. Пропускная способность ребра в остаточном графе иногда называется остаточной пропускной способностью, чтобы ее было проще отличить от пропускной способ- ности соответствующего ребра в исходном потоковом графе G.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Остаточный граф:

  1. СВОБОДА СЕКСУАЛЬНАЯ ОСТАТОЧНАЯ
  2. Граф С. А. Вронский ВВЕДЕНИЕ В АСТРОЛОГИЮ
  3. граф С. А. Вронский. КЛАССИЧЕСКАЯ АСТРОЛОГИЯ Том 3. Домология, 2004
  4. Граф П.А. Валуев как основатель нового подхода к цензуре
  5. граф С. А. Вронский. КЛАССИЧЕСКАЯ АСТРОЛОГИЯ в 12 томах Том 5. ПЛАНЕТОЛОГИЯ.ЧАСТЬII, МЕРКУРИЙ ВЕНЕРА МАРС ЮПИТЕР, 2005
  6. граф С.А. Вронский. КЛАССИЧЕСКАЯ АСТРОЛОГИЯ в 12 томах Том 10. ТРАНЗИТОЛОГИЯ. ЧАСТЬ I ТЕОРИЯ. ТРАНЗИТЫ СОЛНЦА. ТРАНЗИТЫ ЛУНЫ, 2006
  7. 4. От многонациональной империи к остаточному государству: социология в Австрии Национализм, социальные движения и многонациональное государство
  8. ПОСЛЕОБРАЗ
  9. СКОВАHАЯ ДУША
  10. ..Бой часов Вестминстерского аббатства...