ывафыва. Занятие по алгоритмам. Алгоритм ЭдмондсаКарпа это метод фф, но с поиском пути bfs
 Скачать 172.06 Kb.
|
|
3-е занятие по алгоритмам. Алгоритм Эдмондса-Карпа - это метод ФФ, но с поиском пути BFS. Утв. Расстояние(по количеству ребер) от произвольной s до произвольной вершины v в процессе алгоритма не уменьшается. Доказательство. Пусть мы ищем произвольный путь. Заметим, что если мы пустим поток через путь, то вершина не перескочит в слой левее, значит утверждение верно. Рассмотрим сколько раз могло насытиться ребро. Заметим, что если ребро насытилось несколько раз, то между этими насыщениями ребро когда-то разнасытилось, тогда рассмот- рим в каких слоях находятся эти вершины. Значит насыщений ребра могло быть только V 2 . Ребер всего 2E. Значит алгоритм работает за O(V E 2 ) Давайте заметим, что если расстояние от s до t не увеличивается, то нам не надо переза- пускать BFS. Концепция блокирующих потоков - пока у нас есть ненасыщенный путь мы находим слоистую сеть и находим блокирующий поток в слоистой сети. Слоистая сеть - это первая картинка, но мы временно игнорируем обратные ребра и внутри слоя. Блокирующий поток - это такой поток, что мы не можем найти путь, который не содер- жит обратных ребер. Наша концепция завершится, потому что каждая итерация нашего цикла увеличивает рас- стояние между вершинами от s до t, строго увеличится. Рассмотрим алгоритм поиска блокирующего потока. Если ребро насытилось, то мы про него забываем, если мы прошли по ребру и дальше не нашли путь до t, то тоже про ребро забываем. Заметим, что теперь DFS по слоистой сети работает за V + E удаленные . Значит поиск блокирующего потока происходит за V E. Чтобы забывать ребра можно как-то пронумеровать ребра исходящие из каждой вершины и еще хранить число сколько ребер мы забыли. Итоговый алгоритм работает за O(V 2 E) Целочисленные сети. Единичные сети. Давайте посмотрим на алгоритм Диницы, заметим, что мы удаляем все ребра по которым прошли, значит поиск блокирующего будет за E. Давайте заметим, что всего итераций поиска блокирующего потока будет не больше чем 2 √ E. Доказательство Рассмотрим сеть после √ E поиска блокирующего потока, продолжим алгоритм и посмотрим на поток, заметим что все пути больше √ E, значит фаз будет не больше E √ E . Значит в итоге Диница работает за O(V √ E). |