Планарные графы (24-е апреля 2024)

  1. Определения, теоремы
    1. Планарный граф, плоский граф.
    2. Укладка на плоскости − то же, что и укладка на сфере. Любую грань можно сделать внешней.
    3. Теорема Эйлера. E+K+1=V+G. Следствие. E ≤ 3V-6 (у каждой грани хотя бы 3 ребра ⇒ E ≥ 1.5*G ⇒ E+K+1 ≤ V+(2/3)E)
    4. Как выглядит граф, в котором все степени хотя бы 5 и много степеней 6? 6-угольный грид.
    5. Упражнение: двудольный граф? 2V-4
    6. Алгоритмическое следствие: во всех алгоритмах на планарных графах E = O(V).
    7. Теорема Куратовского [1930]: граф планарен iff, не является подразбиением K3,3 или K5.
    8. Теорема Вагнера (аналог Куратовского) [1937]: граф планарен iff, не содержит подграфов стягиваемых к K3,3 или K5.
    9. Теорема Фари [1948]: любой планарный граф можно уложить с использованием только прямых отрезков.
    10. Schnyder [1989]: любой планарный граф при V ≥ 3 можно уложить с использованием только прямых отрезков на гриде размера (V-2)×(V-2). Укладку можно найти за O(V).

  2. [5 минут] Алгоритмы проверки на планарность и выделения граней
    1. Demoucron [1964], O(n2)
    2. Tarjan, Hopcroft [1974], O(n)
    3. Simply O(n): Ulrik Brandes [2011]; LR-Planarity-Testing; Boyer and Myrvold [2004]
    4. Tutte Spring Theorem [1963]: любой трёхсвязный планарный граф однозначно укладывается на плоскость таким образом, что каждая его грань, включая внешнюю, − выпуклый многоугольник, а любая внутренняя вершина − центр масс соседей.

  3. [15 минут] Tutte Spring Theorem: алгоритм укладки прямыми отрезками
    1. Делаем граф трёхсвязным и триангулируем его
    2. Алгоритм укладки: уложить как угодно внешнюю грань, любая другая вершина лежит в центре масс соседей.
    3. Гаусс и метод итерации для решения систем линейных уравнений.
    4. Убираем лишние рёбра.
    5. В чём смысл? Мы система пружин, минимизируем потенциальную энергию. Энергия = выпуклая функция ⇒ минимум существует и единственный.
    6. Почему нет пересечений? Доказательство по индукции: убираем ребро, заменяем вершину степени 2 на ребро.

  4. [10 минут] Алгоритм Демукрона
    1. Нарисовали цикл, выделили компоненты, укладываем компоненты независимо
    2. Укладка компоненты с внешним циклом: нарисовали любой путь путь, разбили цикл на два, компоненту на подкомпоненты, рекурсивно вызвались
    3. Время работы: есть k компонент, на них граф размера k2 противоречий, нужно найти его за O(nk).

  5. [15 минут] Теорема Тарьяна-Липтона о сепараторе в планарном графе
    1. Суть: 23/2n1/2 вершин делят граф на части размера ≤ 2/3n
    2. Следствие 23/2n1/2(1 + (2/3)1/2 + ((2/3)1/2)2 + ...) = 23/2n1/2/(1 - (2/3)1/2) вершин делят граф на части размера ≤ 1/2n
    3. Поиск максимального независимого множества в планарном графе: T(n) = 2Cn1/2*2*T(n/2) = 2C(n1/2 + (n/2)1/2 + ...) = 2Θ(n1/2).
    4. Раскраска в k = O(1) цветов: kΘ(n1/2) = 2Θ(n1/2).
    5. Доказательство теоремы: bfs из ∀ вершины → слои → l1 = разбили на k0 ≤ n/2, k2 ≤ n/2, l0 < l1 : L(l0) + 2(l1-l0) ≤ 2k01/2, l1 < l2 : L(l2) + 2(l2-l1) ≤ 2k21/2. Если l0 ∪ l2 − ответ, закончили. Иначе добавим цикл длины 2(l2 - l0) из конденсированного графа (0...l0) → v и слоёв l0+1..l1-1.
    6. Частный случай и пример, где оценка &Theta(n1/2) достигается: грид, а динамика по профилю по гриду в некотором смысле частный случай идеи "возьмём сепаратор в графе".

  6. [5 минут] Закон Кирхгоффа, Gauss Elimination (George, Rose, Lipton, Tarjan)
    1. Дана сеть из проводников сопротивлений R[i]. Найти сопротивление между s и t.
    2. u[s] = 0, u[t] = 1, ∀v : ∑ R[e]-1(u[v] - u[end[e]]) = 0, u[] − неизвестные.
    3. Часто схема − планарный граф. В планарном графе, где неизвестные − вершины, есть решение системы уравнений за V3/2.
    4. Гаусс для k-диаганальной матрицы за O(nk2)
    5. Как системы уравнений связаны с графами? Вершины = неизвестные; рёбра = ненулевые коэффициенты. Gauss elimination метод : вычёркиваем вершины по одной ; делаем полный граф на соседях. Время вычёркивания = deg2.
    6. Cholesky factorization (decomposition) : A = LLT (L = lower triangular matrix)
    7. Гаусс для графов с сепаратором: сепаратор вычёркиваем в самом конце. n3/2 времени, nlogn памяти (ненулевых элементов).
    8. Вариации: пусть C − сепаратор, A и B − половинки, можно рекурсивно запускаться от A и B, а можно от A+C и B+C, но при этом вершины C считать уже пронумерованными.
    9. Гаусс и параллелизм.

  7. [10 минут] Алгоритм выделение граней плоского графа
    1. Пример задачи: пересечь два невыпуклых многоугольника. Решение за O(n2logn).
    2. Данные: вершины xi, yi и рёбра между вершинами.
    3. Алгоритм за O(n): храним для каждого орребра next (по углу) и reversed, жадно идём : e → next[reversed[e]] по непосещённым рёбрам, чтобы выделить очередную грань.
    4. Внешняя грань = грань с отличающимся знаком площади