Динамические деревья: различия между версиями

Вначале Слейтор и Тарьян использовали динамические деревья для алгоритма блокирующего потока Диница [   ]. Динамические деревья используются для поддержки леса ребер с положительной остаточной емкостью. Как только источник s и сток t становятся элементами одного и того же дерева, алгоритм посылает максимально возможный поток по пути s-t; это снижает до нуля остаточную емкость по меньшей мере одного ребра, которое затем можно отрезать от дерева. С тех пор было предложено несколько алгоритмов с максимальной и минимальной стоимостью потока, включающих динамические деревья (например, в [9, 15]). Динамические структуры данных (в особенности основанные на стягивании дерева) также широко используются в динамических графовых алгоритмах – таких как динамические версии построения минимальных остовных деревьев [6,10], связности [ ], двусвязности [ ] и двудольности [10]. В числе других областей применения можно упомянуть оценку динамических деревьев выражений [ ] и стандартные алгоритмы на графах [13].