Продвинутые алгориты на графах

  1. [5 минут] Анонс. Выбор тех, кто пишет конспект.
  2. [5 минут] bfs на [K..2K] рёбрах
    1. 1-k bfs нигда не пользовался целочисленностью рёбер
    2. A..B → 1..B/A
    3. 0..1 ↔ R
  3. [15 минут] Алгоритм Карпа поиска цикла минимального среднего веса
    1. μ = minv maxk (d[n,v] - d[k,v]) / (n - k); вычтем из всех рёбер x, μ уменьшится ровно на x
    2. Доказываем для случая μ = 0, знаменатель сразу уходит, нужно доказать (а) d[n,v] ≥ mink, (б) ∃v : d[n,v] = mink
  4. [15 минут] Алгоритм Джонсона и потенциалы
    1. Потенциалы. Кратчайший путь остался кратчайшим. Вес цикла не изменился.
    2. Алгоритм Джонсона: фиктивная вершина + FB + применили расстояния, как потенциалы
    3. Теорема: поиск расстояний из вершины v равносилен поиску таких потенциалов, что есть ориентированное остовное дерево с корнем v веса ноль
--- Перерыв ---
  1. [45 минут] Алгоритм Гольдберга
    1. Анонс: делаем алгоритм за O(EV1/2logN) для целых весов, сперва научимся за O(EV1/2) делать для весов [-1..∞)
    2. Суть − найти правильные потенциалы, будем по чуть-чуть избавляться от отрицательных рёбер. Сперва за O(VE).
    3. Берём вершину v, в которую есть входящее ребро -1, меняем ей потенциал на -1.... Входящим рёбрам ок, а исходящим? Придётся взять всю компоненту, достижимую из v по 0 и -1 рёбрам.
    4. Как ускорить? Одним махом за O(E) лечить не одну вершину, а пачку O(k1/2) вершин, где k − число вершин с отрицательными рёбрами.
    5. Сжали компоненты сильной связности по 0 и -1, в конденсации запустили динамику, считающую расстояние от фиктивной вершины s в графе с -1 и 0 рёбрами.
    6. Или есть путь длины -k1/2, или есть слой (вершины на одинаковом расстоянии) из k1/2 вершин
    7. Скорость сходимости (сколько раз нужно из числа вычесть его корень?)
    8. Слой: очевидно
    9. Путь: с конца в начало идём и делаем S1, S2, ... St добавление -1 к потенциалу. (Si − посещённые на i-м шаге вершины, Si ⊂ Si+1)