Алгоритмы на графах (10-е апреля 2024)

  1. Вероятностная проверка на 3-связность за O(n+m).
    1. Построение: остов, случайные веса, dp по остову, чтобы XOR вершин был ноль
    2. Основная лемма: XOR разреза ноль
    3. Следствия: мост, 2-разрез, 3-разрез
    4. В другую сторону XOR не разреза равновероятный
    5. Задача: как проверить, потеряется ли связность при удалении множества рёбер A, |A|=O(1)?

  2. Эппштейн: поиск k-го непростого пути.
    1. Кратчайший путь. Картинка с ответвлениями. Вес ответвлений.
    2. Какие кандидаты добавятся?
    3. Персистентная сливаемая куча кандидатов.

  3. Алгоритм двух китайцев (остовное ориентированное MST за O(mlogn)).
    1. Основа с вычитанием. O(mn).
    2. Версия за O(mlogn) для получение веса дерева
    3. Восстановление рёбер дерева: итеративное расжатие
    4. Восстановление рёбер дерева: алгоритм Прима на весах "время сжатия"

  4. Динамическая связность для орграфов
    1. Просто найти матричку: O(nm/w).
    2. Только добавления: O(n/w) амортизированно на запрос.
    3. King,Sagert'1999, fully-dynamic O(n2)-update, O(1)-query for DAG
    4. Люди сомневаются, что full-dynamic SCC можно за O(m1-eps) и на update, и на query (даёт мощный прогресс в SETH).
− Перерыв −
  1. Динамическая связность для орграфов (продолжение)
    1. Shiloach'1981 : решение decremental-SSR (single-source-reachability) за O(q + nm)
    2. [skipped] Italiano'2001 : храним отложенные операции, оптимум достигается при k=n0.575 отложенных, это следует из уравнение на степень n в умножении матриц w(1,eps,1)=1+2eps

  2. Динамическая связность и 2-связность в оффлайн за O((n+m)logn).
    1. Откаты: решение дерева отрезков за O(log2n).
    2. Упражнение: точки добавляются и удаляются, поддерживать две самые ближайшие.
    3. Сжатие графа. Решение деревом отрезков за O(logn).
    4. Упражнение: Обобщение для двусвязности.
    5. Упражнение: Обобщение для MST.

  3. Динамическая связность в онлайн за O(log2n)
    1. Наивное Add = O(1), Del = O(1), Get = O(m)
    2. Наивное Add = DSU, Del = O(n+m), Get = DSU
    3. ETT : всё за log, но мы всегда лес
    4. ETT : напоминание, как это добро хранить в Treap, что нужны отцы, подниматься до корня
    5. Проблема : как при удалении искать замену?
    6. Основная идея : переберём рёбра, торчащие из меньшего из кусков, при этом перебирать можно только вершины, из которых что-то торчит (сумма в декартовом дереве больше нуля)
    7. Как самортизировать? Всем рёбрам, которые перебрали будем понижать "ранг".
    8. Конструкция: У каждого ребра есть ранг от log2n..0. При добавлении равен log2n.
    9. Для каждого k = 0..log2n мы поддерживаем ET[k] − MST на рёбрах с рангом 0..k. ET[log2n] = полный остов.
    10. ET[i] ⊂ ET[i+1]. Если ребро ранга i или не в остовах, или присутствует в ET[i],ET[i+1],ET[i+2]...
    11. Инвариант: компоненты ET[i] имеют размер не более 2i.
    12. Поиск замены на уровне j ≥ i:
      1. ET[j]=A+B, выбрать меньшую половину B
      2. Понизить ранг рёбрам B до i-1 (|B| ≤ 2i-1, между A и B нет рёбер ранга меньше j).
      3. Перебирать рёбра ранга j, торчащие из B, понижать им ранг до i-1, если ведут в B, если же ведут в A, добавлять в остовы j..log2n
    13. Запросы, построение
      1. База: на каждом уровне каждая вершина лежит в своём декартовом дереве, состоящим только из этой вершины. Рёбер нет.
      2. Ответ на запрос get(a,b): getRoot(vertexPosition[a, 0]) == getRoot(vertexPosition[b, 0])
      3. Запрос add(a, b): if (!get(a, b)) { новое ребро = {a, b, rank=0}; makeRoot(a); makeRoot(b); merge(getRoot(a), новое ребро, getRoot(b), новое ребро) }
      4. Запрос del(a, b): e = ребро; i = rank[e]; if (e не в ET[i]) return; for (j=i..log2n) { ET[j].splitByEdge(e); } найти замену для "e"!

  4. Дерево доминаторов за O(mlogn).
    1. Определение доминаторов, естественный поиск за O(mn/w).
    2. Наша задача не проще LCA.
    3. Решение для DAG: LCA
    4. Решение для произвольного графа: LCA много раз (не более 6 фаз)
    5. Свойства доминаторов: ребро вверх в дерево dfs ; вложенность отношения "доминатор".
    6. Решение для произвольного графа: через LCA-offline (dfs+DSU) сведение к задаче на пути.
    7. Решение для задачи на пути.