ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Michael Ryazanov                     2:5030/1492.64 08 Apr 2003  00:13:00
 To : All
 Subject : Все потоки
 -------------------------------------------------------------------------------- 
 

 
    Читаем в местном FAQ'е о графах:
 * 9. Потоки в сетях. *
 
 Q:> * 9.1. Задача. *
 
     Определить максимальный поток, протекающего  от  вершины-источника  s
  орграфа к вершине-стоку t. При этом каждой дуге *(i, j)* орграфа приписана
  _пропускная способность_ *c[i, j]* определяющая максимальное значение  потока,
  протекающего по этой дуге.
 
 A:> (по *[1]* )
 
    * 9.2. Теорема Форда-Фалкерсона*
 
     _Разрез_ - множество дуг,удаление которых приводит к разрыву всех путей из
  s в t.
     _Пропускная способность разреза_ - суммарная пропускная способность дуг его
  составляющих.
     Справедлива следующая
     *Теорема  Форда-Фалкерсона*. Величина каждого потока  из  s  в  t   не
  превосходит пропускной способности минимального разреза,разделяющего s и t,
  причем существует поток, достигающий этого значения.
     Т.о. задачи нахождения макс. потока и мин. разреза эквивалентны.
 
    * 9.3. Решение. *
 
     *"Техника меток" Форда и Фалкерсона*   <...>
 Теперь собственно вопросы:
    1. Как найти матрицу всех максимальных потоков (т.е. максимальные потоки для 
 всех пар s и t)? Матрица c[i, j] пусть будет симметричной (граф
 неориентированный) и целочисленной.
    2. Как обновить искомую матрицу после изменения пропускной способности ребра?
 
                                                                       |V|uxau/\
 --- -- - ъ
  * Origin:             Ф И З Ф А К - Ч Е М П И О H !           (2:5030/1492.64)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор