Планарные графы (27-е мая 2019)

  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. Упражнение: двудольный граф? 2V-4
    5. Алгоритмическое следствие: во всех алгоритмах на планарных графах E = O(V).
    6. Теорема Куратовского [1930]: граф планарен iff, не является подразбиением K3,3 или K5.
    7. Теорема Вагнера (аналог Куратовского) [1937]: граф планарен iff, не содержит подграфов стягиваемых к K3,3 или K5.
    8. Теорема Фари [1948]: любой планарный граф можно уложить с использованием только прямых отрезков.
    9. 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. [10 минут] Tutte Spring Theorem: алгоритм укладки прямыми отрезками
    1. Делаем граф трёхсвязным и триангулируем его
    2. Алгоритм укладки: уложить как угодно внешнюю грань, любая другая вершина лежит в центре масс соседей.
    3. Гаусс и метод итерации для решения систем линейных уравнений.
    4. Убираем лишние рёбра

  4. [10 минут] Алгоритм Демукрона
    1. Нарисовали цикл, выделили компоненты, укладываем компоненты независимо
    2. Укладка компоненты с внешним циклом: нарисовали любой путь путь, разбили цикл на два, компоненту на подкомпоненты, рекурсивно вызвались

  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. [5 минут] Закон Кирхгоффа
    1. Дана сеть из проводников сопротивлений R[i]. Найти сопротивление между s и t.
    2. u[s] = 0, u[t] = 1, ∀ v : ∑ R[e]-1(u[v] - u[end[e]]) = 0, u[] − неизвестные.
    3. Часто схема − планарный граф. В планарном графе, где неизвестные − вершины, есть решение системы уравнений за {unknownvariable:v3/2}.

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