СНМ и Остовные деревья (4 марта 2025)

1. [35 минут] Краскал и DSU
   1. Алгоритм Краскала : жадность
   2. Доказательство: рассмотрим оптимальный ответ, сделаем замену
   3. Прим = модификация Дейкстры, где d[v] = "max входящий вес"
   4. Реализация Прима за ElogV и V² (более быстрые на практику)
   5. Доказательство: от противного
   6. Обобщение доказательства : лемма о разрезе (∃ MST, содержащее всё уже выбранное и "e")
   7. Борувка = итеративное сжатие графа. Добавляем рёбра по одному в правильном порядке.
   8. Борувка за min(V², ElogV)
   
   
2. [15 минут] Реализация Краскала, DSU
   1. Решение списками: меньшее к большему, join суммарно за O(nlogn), get за O(1)
   2. Решение деревьями. Эвристика "меньшее к большему" и ранговая версия.
   3. Решение деревьями. Эвристика "сжатие путей".
   4. Практически эффективная реализация

1. [35 минут] DSU. Доказательства
   1. Эвристика сжатия путей. Доказательство O(logn) для этой эвристики (смотрим на количество тяжёлых рёбер).
   2. Эвристика "меньшее к большему". Варианты с рангами и размерами. Доказательство O(logn) для get.
   3. Две эвристики O(mlog^*n)
   4. Введение обратной функции Аккермана (только определение)
   5. Две эвристики O(m + nlog^*n)
   
   
2. [15 минут] Алгоритм Йена'71 поиска k-го объектра
   1. k-й путь за O(Vk*Dijkstra)
   2. [skipped] k-й остов за O(Ek*MST)

Дополнительная лекция

1. [15 минут] Эппштейн для k-го непростого пути
   1. Пример с динамикой
   2. Решение за O((n+m+k)log(nk))
   
   
2. [30 минут] DSU: обратная функция Аккермана
   1. Доказываем log^*(log^*n) + 2, log^*(log^*(log^*n)) + 3...
   2. Получаем "сколько раз нужно взять log^*x, чтобы число итераций было больше результата"
   3. Вводим функцию Аккермана и обратные ей. Показываем основные свойства.
   4. Доказываем функцию Аккермана.