Лекция 6. Потоки. Алгоритм Диница

• Приветствие зрителей и проверка чатика.  

• Проблемы с задержкой и настройка камеры.  

• Призыв к зрителям писать вопросы в чатик.  

• Напоминание о предыдущем алгоритме Эдмонса-Карпа.  

• Описание графа и пропускных способностей.  

• Процесс построения потока и увеличения его вдоль пути.  

• Обсуждение улучшения алгоритма двумя путями: масштабирование и применение DFS.  

• Введение в масштабирование: поиск путей длиной больше 2^k.  

• План на сегодня: улучшение алгоритма для более быстрого нахождения путей.  

• Построение графа кончащих путей с помощью BFS.  

• Оставление только ребер, лежащих на кратчайших путях.  

• Утверждение о том, что все пути длины d можно найти в этом графе.  

• Поиск любого пути из S в T на графе кончащих путей.  

• Дополнение потока вдоль найденного пути.  

• Удаление ребер, которые больше не участвуют в кратчайших путях.  

• Тупики не участвуют в кратчайшем пути, поэтому их можно удалять.  

• Удаление тупиков каскадно, чтобы поддерживать сеть без тупиков.  

• Это позволяет быстро находить кратчайшие пути.  

• Алгоритм Денница использует слоистую сеть для поиска кратчайших путей.  

• Слоистая сеть содержит только кратчайшие пути, что ускоряет поиск.  

• Алгоритм включает построение слоистой сети и удаление тупиков.  

• На каждой фазе Денница находятся пути длины d.  

• Время работы фазы оценивается как O n^2.  

• Удаление тупиков и дополнение вдоль пути работают за O n^2.  

• Алгоритм Денница можно масштабировать для улучшения времени работы.  

• Время работы будет O n^2 log n.  

• Наука не смогла значительно улучшить алгоритм, несмотря на длительные исследования.  

• Обсуждение текущего алгоритма, который имеет логарифмическую сложность.  

• Введение нового алгоритма, который будет работать лучше.  

• План использования деревьев для оптимизации.  

• Описание проблемы с текущим алгоритмом.  

• Необходимость найти дополняющий путь и минимальное ребро.  

• Уменьшение всех ребер на минимальное ребро и удаление нулей.  

• Применение деревьев для оптимизации.  

• Описание структуры данных и операций с деревьями.  

• Использование операции экспоз для объединения путей в одно дерево.  

• Построение путей из зала в виде одного дерева.  

• Применение операций на деревьях для минимизации сложности.  

• Оптимизация внутри итераций.  

• Построение деревьев для каждой вершины.  

• Поддержка множества ребер в виде деревьев.  

• Перестройка деревьев при необходимости.  

• Пример использования деревьев для хранения путей.  

• Применение операции экспоз для объединения путей.  

• Уменьшение ребер на минимальное ребро и удаление нулей.  

• Рассматривается алгоритм поиска минимального ребра в дереве.  

• Если ребро не найдено, дерево наращивается.  

• Если ребро найдено, оно удаляется и дерево уменьшается.  

• Если ребро не найдено, вершина удаляется.  

• Алгоритм повторяется до тех пор, пока не будет найден путь.  

• Оптимизация включает повторное использование ребер из предыдущих путей.  

• Оценивается время работы алгоритма.  

• Алгоритм запускается не более nm раз.  

• Операция линк добавляет ребро в дерево, которое затем удаляется.  

• Алгоритм можно улучшить, чтобы уменьшить логарифм.  

• Важно поддерживать маленькие деревья для уменьшения времени работы.  

• Разделение деревьев может быть полезным для оптимизации.  

• Рассматривается граф, где все веса равны единице.  

• Это часто встречающийся случай, где по каждому ребру либо есть поток, либо нет.  

• Пример: алгоритм Форда-Фалкерсона работает быстрее на таких графах.  

• Алгоритм Форда-Фалкерсона увеличивает поток на единицу на каждой итерации.  

• На графах с единичными весами размер потока не превышает n-1.  

• Это позволяет алгоритму работать быстрее, чем на графах с ненулевыми весами.  

• На графах с единичными весами алгоритм работает существенно быстрее.  

• Каждая итерация увеличивает поток на единицу, что приводит к исчезновению ребер.  

• Это позволяет сократить количество итераций и улучшить производительность.  

• Количество итераций может быть меньше, чем на графах с ненулевыми весами.  

• Это особенно актуально для разреженных графов, где m меньше n^2.  

• Доказательство этого утверждения будет представлено далее.  

• Доказывается, что число итераций не превышает m^1/2.  

• Объясняется, что после корня из m итераций, расстояние от источника до стока становится больше, чем m^1/2.  

• Это позволяет найти хотя бы один дополняющий путь на каждой итерации.  

• Доказательство показывает, что после корня из m итераций, количество оставшихся итераций не превышает m^1/2.  

• Это подтверждает, что алгоритм работает быстрее на графах с единичными весами.  

• Для второго свойства нужно, чтобы не было параллельных ребер.  

• Оценка зависит только от n, а не от m.  

• Если есть параллельные ребра, оценка становится сложной.  

• Рассматривается слоистая сеть после операции.  

• Вершины на расстоянии 1, 2, 3 и 4.  

• Доказывается, что в графе есть небольшой разрез.  

• Находим минимальный разрез между слоями.  

• Оцениваем количество ребер между слоями.  

• Минимум по всем парам слоев.  

• Количество ребер не больше произведения мощностей множеств.  

• Минимум максимален, когда все множества равны.  

• Оценка количества ребер через n и d.  

• Если нет параллельных ребер, то разрез не больше n в степени две третьих.  

• Новые итерации требуют не больше одного пути.  

• Обсуждение дальнейших шагов и алгоритмов.  

• Обсуждение слоистых сетей и тупиков.  

• Тупики бывают двух типов: те, из которых ничего не выходит, и те, в которые ничего не входит.  

• План по убийству тупиковых вершин.  

• Введение понятия "минимальный поток" для вершин.  

• Подсчет минимального потока для каждой вершины.  

• Пример расчета минимального потока для вершины с входящими и исходящими ребрами.  

• Выбор вершины с минимальным потоком.  

• Преобразование вершины в тупик путем пропихивания потока через нее.  

• Пример пропихивания потока через вершину с входящими и исходящими ребрами.  

• Проталкивание потока через ребра.  

• Пример пропихивания потока через ребра и его распределение по нижним слоям.  

• Преобразование избыточного потока в тупики.  

• Удаление вершин и ребер после пропихивания потока.  

• Оценка времени выполнения процедуры.  

• Обсуждение других алгоритмов для проталкивания потока.  

• Практическое применение алгоритмов проталкивания потока.  

• Обсуждение других алгоритмов и их особенностей.  

• Вопросы и планы на будущее.  

• Планы на семинары и лекции.  

• Обсуждение сдачи заданий на разных языках программирования.  

• Прощание и завершение трансляции.