MST

  1. Формулируем задачу
  2. [10 минут] Краскал за sort + m*DSU
  3. [10 минут] Прим за O(Dijkstra)
  4. [10 минут] Борувка: у каждой вершины
  5. [10 минут] Док-во времени работы борувки min(ElogV, V2)
--- Перерыв ---
  1. [20 минут] Доказательства алгоритмов
    1. Через любой разрез можно выбрать минимальное ребро (берём остов, добавляем ребро, видим цикл, удаляем другое ребро через этот же разрез)
    2. Дополнение к лемме: разрез мог уже иметь частично построенный остов... ребро всё равно брать выгодно
    3. Через лемму доказали Краскала, Прима, Борувку
  2. [20 минут] Доказательство c обратной функцией Аккермана
    1. Вводим прямую функцию Аккермана, оцениваем A1, A2, A3
    2. Вводим прямую обратную Аккермана
    3. Вводим потенциал для оценки СНМ (level, iter)