Реализация алгоритмов вычисления величины всплеска (burst) в древовидных сетях: базового O(k·n) и оптимизированного O(n log n) с использованием техники Small-to-Large.
Дипломная работа: «О стационарных и динамических потоках в древовидных сетях»
Южный федеральный университет, Институт математики, механики и компьютерных наук им. И.И. Воровича
Научный руководитель: проф., д. ф.-м. н. Скороходов Владимир Александрович
Автор: Ивахненко Владимир Михайлович
Год: 2026
Ссылка на работу в репозитории ЮФУ: https://hub.sfedu.ru/repository/material/801352166/
Рассмотрим древовидную сеть T с корнем-источником s. Каждое ребро (u, v) имеет пропускную способность c(u, v). Поток f в такой сети определяется для каждого ребра значением 0 ≤ f(u, v) ≤ c(u, v), причём в каждом внутреннем узле выполняется условие баланса:
∑ f(u, v) = f(parent(u), u) для каждого внутреннего u ≠ s
v ∈ A(u)
Величина всплеска — это суммарный объём дополнительного потока, который может быть направлен к листьям, находящимся на разной глубине, при нарушении баланса. Формально, всплеск вычисляется как:
Burst = Σ F^(d)_max
d ∈ D
где D — множество уникальных глубин листьев, а F^(d)_max — максимальный поток, достижимый к листьям на глубине d.
В работе получены следующие основные результаты:
-
Необходимое условие возникновения всплеска (Теорема 4): всплеск возможен только если:
- существуют листья различной глубины (|D| > 1),
- суммарная пропускная способность дуг, входящих в стоки, превышает F_max,
- сеть не является сбалансированной.
-
Точная формула величины всплеска (Теорема 5): в момент времени t* = L_max (максимальная глубина стока) величина динамического потока равна:
V(φ, t*) = Σ F^(d)_max d ∈ D
Всплеск возникает тогда и только тогда, когда Σ F^(d)_max > F_max.
Наивный подход: для каждой уникальной глубины d вычисляется максимальный поток F^(d)_max отдельным проходом «снизу вверх» (bottom-up DP). Общая сложность — O(k · n), где k — число различных глубин листьев, n — число вершин.
Для каждой уникальной глубины d:
dp[v] = ∞, если depth(v) = d и v — лист
dp[v] = 0, иначе (для листьев)
dp[u] = Σ min(c(u,v), dp[v]) для внутренних u (bottom-up)
Burst += dp[root]
Недостаток: в худшем случае k = Θ(n) (гребёнка), что даёт квадратичную сложность O(n²).
Вместо k отдельных проходов используется один проход с техникой Small-to-Large merge. Для каждого узла u хранится отображение M[u]: глубина → вклад в поток. При обработке узла:
- Выбирается ребёнок v_max с наибольшим |M[v]|.
- M[u] получает содержимое M[v_max] (move semantics — O(1)).
- Для каждого остального ребёнка v: элементы M[v] сливаются в M[u].
- Значения в M[u] усекаются: M[u][d] = min(c(u, v_max), M[u][d]).
Общая сложность — O(n log n) за счёт Small-to-Large: каждый элемент перемещается не более ⌈log₂ n⌉ раз.
├── main.cpp # Ядро: C++ реализация алгоритмов + бенчмарки
├── demo.html # Интерактивная визуализация (HTML/Canvas/JS)
├── plot.py # Построение графиков (combined plot)
├── plot2.py # Построение графиков (отдельные файлы)
├── experiment_results.txt # Результаты бенчмарка (N, k, время)
├── benchmark_results.csv # Детальные результаты замеров
├── abs_time.png # График: абсолютное время работы
├── asymptotic.png # График: верификация асимптотики
└── burst_complexity_analysis.png # Комбинированный график сложности
- C++ компилятор с поддержкой C++17 (g++, clang++, MSVC)
- Python 3 + matplotlib (только для построения графиков)
g++ -O2 -std=c++17 -o experiment main.cpp
./experimentРезультаты сохраняются в experiment_results.txt.
pip install matplotlib numpy
# Комбинированный график (2 панели)
python plot.py
# Отдельные графики
python plot2.pyСохраняются: burst_complexity_analysis.png, abs_time.png, asymptotic.png.
Бенчмарк проведён на структуре данных «гребёнка» (comb tree) — дерево, максимально способное проявить burst-эффект.
| N (вершин) | k (уник. глубин) | Базовый O(k·n) (мс) | Оптимизированный O(n log n) (мс) | Ускорение |
|---|---|---|---|---|
| 1 000 | 500 | 1 | 0 | — |
| 2 000 | 1 000 | 5 | 1 | 5× |
| 4 000 | 2 000 | 21 | 6 | 3.5× |
| 8 000 | 4 000 | 82 | 27 | 3× |
| 16 000 | 8 000 | 328 | 119 | 2.8× |
| 32 000 | 16 000 | 1 315 | 459 | 2.9× |
| 64 000 | 32 000 | 5 701 | 1 993 | 2.9× |
| 128 000 | 64 000 | 31 258 | 7 868 | 4× |
Абсолютное время работы:
Верификация асимптотики (нормализованное время):
Нормализованное время T/N² (базовый) и T/(N log N) (оптимизированный) стремится к константе, что подтверждает теоретические оценки сложности.
- Параллельная анимация двух алгоритмов на одном дереве
- Настройка размера дерева (N = 8..24), типа (гребёнка / сбалансированное), скорости
- Пошаговый режим (кнопка «Шаг»)
- Запись анимации в WebM-видео с возможностью скачивания
- Отображение промежуточных состояний: значения dp[u] для базового, содержимое M[u] для оптимизированного
#Контакты
Автор: Ивахненко Владимир Михайлович Email: der.w3@yandex.ru GitHub: Vladimir Ivakhnenko