�ݺ�ߣ

Визуализация графов
Computer Science клуб, март 2014
Александр Дайняк, ФИВТ МФТИ
www.dainiak.com

Планарные графы
Планарный граф — это граф, для которого существует плоская
укладка без пересекающихся рёбер.
Например, граф планарный

Планарные графы
Грань плоской укладки — это область плоскости, отделяемая
укладкой.
Пример:
1
3
5
42

𝑘-связность
𝑘-связный (𝑘-вершинно-связный) граф — это такой связный граф, что чтобы
сделать его несвязным или одновершинным, нужно удалить не менее 𝑘
вершин.
Тривиальные наблюдения:
• 1-связные графы — это то же, что и связные графы
• Если граф (𝑘 + 1)-связен, то он и 𝑘-связен
• Если из 𝑘-связного графа удалить любые 𝑙 вершин, то граф останется по
крайней мере (𝑘 − 𝑙)-связным
Нетривиальное наблюдение — теорема Менгера:
Граф является 𝑘-связным т. и т.т., когда любую пару вершин графа можно
соединить 𝑘 цепями, не имеющими общих внутренних вершин.

Циклы в планарных графах
Утверждение.
Пусть в некоторой укладке планарного графа внутри некоторого
цикла 𝐶 лежит множество рёбер 𝐸𝑖𝑛𝑡, а снаружи множество рёбер 𝐸𝑒𝑥𝑡.
Тогда существует и укладка этого графа, в которой внутри 𝐶 лежат
рёбра 𝐸𝑒𝑥𝑡, а снаружи рёбра 𝐸𝑖𝑛𝑡.
Пример:

Циклы в планарных графах
Идея доказательства.
Сначала деформируем изображение графа, так, чтобы изображение
цикла 𝐶 стало окружностью, и при этом через центр окружности
не проходили никакие рёбра.
Затем выполняем инверсию плоскости относительно этой окружности.

Стягивание рёбер
• Граф 𝐺 является стягиваемым к графу 𝐺′, если 𝐺′ можно
получить из 𝐺, применив некоторое количество раз операцию
стягивания ребра
• Если граф 𝐺 планарен, то и граф 𝐺′
планарен:

Миноры
• Граф 𝐻 является минором графа 𝐺, если в 𝐺 есть подграф 𝐻′,
который можно стянуть к 𝐻
𝐺𝐻 𝐻′

Триангуляции
Триангуляция — это граф, в укладке которого каждая грань
ограничена треугольником (в «графовом», а не геометрическом
смысле).

Если в планарном графе на 𝑛 вершинах менее 3𝑛 − 6 рёбер, то
в граф можно добавить ребро, так, чтобы он остался планарным.
Доказательство.
Если в графе менее 3𝑛 − 6 рёбер, то в его укладке есть грань,
граница которой не является треугольником.
В этой грани можно провести новое ребро.

Если в планарном графе на 𝑛 вершинах менее 3𝑛 − 6 рёбер,
то в граф можно добавить ребро, так, чтобы он остался планарным.
В любой триангуляции на 𝑛 вершинах ровно 3𝑛 − 6 рёбер.
Любой планарный граф является подграфом некоторой
триангуляции.

Триангуляции трёхсвязны
Любая триангуляция (на более чем трёх вершинах) трёхсвязна.
Доказательство.
Пусть 𝐺 — триангуляция.
Предположим, что граф 𝐺 не трёхсвязен, и придём к противоречию.

Если 𝐺 не двухсвязен, то в 𝐺 есть концевой блок 𝐵,
имеющий с остальной частью 𝐺′
графа 𝐺 единственную общую
точку сочленения 𝑣.
Рассмотрим укладку 𝐺, в которой 𝑣 лежит на внешней грани.
У 𝐵 и 𝐺′
есть соответственно вершины 𝑥 и 𝑦 (𝑥, 𝑦 ≠ 𝑣) на внешней
грани. При этом 𝑥𝑦 ∉ 𝐸 𝐺 , но можно добавить ребро 𝑥𝑦 в укладку.
Это противоречит тому, что триангуляция является максимальным
планарным графом.
𝐺′
𝐵
𝑣 𝑥
𝑦

Итак, 𝐺 двухсвязен.
Если 𝐺 не трёхсвязен, то можно выделить подграф 𝐺′, который
имеет с остальной частью 𝐺′′ графа 𝐺 только две общие вершины
𝑢, 𝑣.
𝑣
𝑢
𝐺′
𝐺′′

Граф 𝐺′′ + 𝑢𝑣 является минором 𝐺.
Аналогично, 𝐺′ + 𝑢𝑣 является минором 𝐺.
Т.к. 𝐺 планарен, то графы 𝐺′ + 𝑢𝑣 и 𝐺′′ + 𝑢𝑣 планарны.
𝑣
𝑢
𝐺′
𝐺′′

Возьмём укладки графов 𝐺′ + 𝑢𝑣 и 𝐺′′ + 𝑢𝑣 , в которых ребро 𝑢𝑣
лежит на границе внешней грани.
Из них можно построить укладку 𝐺, в которой на внешней грани
есть пара вершин 𝑥 и 𝑦, отличных от 𝑢, 𝑣, и не соединённых ребром.
Это противоречит тому, что 𝐺 — триангуляция.
𝑣
𝑢
𝐺′
𝐺′′
𝑦
𝑥

Укладки двусвязных графов
В любой укладке двусвязного графа граница каждой грани является
простым циклом.

Теорема Татта о комбинаторном критерии
«гранности»
Теорема. (Tutte ’1963)
В укладке трёхсвязного планарного графа 𝐺 подграф 𝐵 образует
границу грани т. и т.т., когда выполнены два условия:
• 𝐵 является порождённым простым циклом в 𝐺
(то есть у 𝐵 нет «хорд» в 𝐺),
• граф 𝐺 − 𝐵 связен.

Укладки трёхсвязных графов
Доказательство:
Зафиксируем произвольную плоскую укладку трёхсвязного графа 𝐺.
Пусть 𝐶 — цикл, не являющийся границей грани.
Тогда есть непустые множества рёбер внутри 𝐶 и снаружи 𝐶.
Получаем, что либо у 𝐶 есть хорда, либо найдутся какие-то вершины
𝑢 и 𝑣 внутри и снаружи 𝐶 соответственно.
Любой путь из 𝑢 в 𝑣 пересекает 𝐶, а значит граф 𝐺 − 𝐶 не будет
связным.

Пусть 𝐵 — цикл, являющийся границей грани.
Можно считать, что 𝐵 — граница внешней грани укладки 𝐺.
Если у 𝐵 есть хорда 𝑥𝑦, то граф 𝐺 − 𝑥, 𝑦 несвязен —
противоречие с трёхсвязностью 𝐺:
𝑥
𝑦

Итак, у 𝐵 нет хорд. Осталось доказать связность графа 𝐺 − 𝐵 .
Допустим противное. Тогда существуют 𝑢, 𝑣 ∈ 𝑉 𝐺 − 𝐶 ,
такие, что любой путь из 𝑢 в 𝑣 имеет с 𝐵 общую вершину.
Так как 𝐺 трёхсвязен, то найдутся пути 𝑃1, 𝑃2, 𝑃3 между 𝑢 и 𝑣 без
общих внутренних вершин. Пусть 𝑥𝑖 — любая из общих вершин
пути 𝑃𝑖 и цикла 𝐵.

Получаем, что в 𝐺 есть не пересекающиеся по внутренним
вершинам пути из 𝑢, 𝑣 в каждую из вершин 𝑥1, 𝑥2, 𝑥3.
Возьмём точку вне 𝐵 и соединим её с 𝑥1, 𝑥2, 𝑥3:
Получили укладку графа, гомеоморфного 𝐾3,3 — противоречие.
Теорема Татта доказана.
𝑢
𝑣
𝑥1
𝑥2
𝑥3

Теорема Татта «о резиновой укладке»
Теорема. (Tutte ’1963 — Tutte’s rubber band embedding)
Пусть Γ — множество вершин трёхсвязного планарного графа,
составляющее границу одной из граней в какой-нибудь укладке.
Тогда укладку графа можно получить, если закрепить вершины Γ
в вершинах произвольного выпуклого многоугольника,
и представить, что рёбра графа стремятся стянуться, как резинки.
Полученная при стабилизации такой физической системы
«картинка» и будет искомой укладкой.

Укладки графов платоновых тел,
полученные методом Татта

Факт 1: связность частей картинки,
отсекаемых прямой
Факт 1:
Пусть 𝑙 — произвольная прямая.
Пусть 𝑇 — множество вершин 𝐺, лежащих в одной и той же
открытой полуплоскости относительно 𝑙.
Тогда граф 𝐺 𝑇 связен.

Иллюстрация к доказательству Факта 1

Доказательство Факта 1
Пусть 𝑢, 𝑣 — пара вершин 𝐺, попавших по одну сторону от 𝑙.
Пусть Γ′
— вершины из Γ, лежащие в одной полуплоскости с 𝑢, 𝑣.
Достаточно доказать, что от 𝑢 можно дойти до Γ′
, двигаясь только
по вершинам по одну сторону от 𝑙.
Действительно, тогда окажется, что и для 𝑣 так можно сделать.
Поскольку Γ′ связно (это цепь), то значит между 𝑢 и 𝑣 можно
пройти, оставаясь по одну сторону от 𝑙.

Б.о.о. считаем, что 𝑙 не параллельна никакому ребру в укладке 𝐺.
Случай 0. Если 𝑢 ∈ Γ′, то доказывать нечего.
Случай 1. Пусть 𝑢 ∉ Γ, и есть вершина 𝑤 ∈ 𝑁 𝑢 , т.ч. 𝑥 𝑤 ≠ 𝑥 𝑢.
Можно считать, что 𝑤 в одной полуплоскости с 𝑢, но дальше от 𝑙.
Перейдём в 𝑤 и продолжим по индукции.
Случай 2. Пусть 𝑥 𝑤 = 𝑥 𝑢 для любого 𝑤 ∈ 𝑁 𝑢 . Положим
𝑈 ≔ 𝑢′ ∈ 𝑉 𝐺 ∣ 𝑥 𝑢′ = 𝑥 𝑢 .
Пусть 𝐻 — компонента графа 𝐺 𝑈 , содержащая 𝑢.
Если 𝐻 ∩ Γ′ ≠ ∅, то всё получилось. Иначе, пусть 𝑢′′ — одна из вершин,
за которые 𝐻 прицепляется к 𝐺 − 𝐻 . Тогда у 𝑢′′
есть сосед, лежащий в одной
полуплоскости с 𝑢′′, но дальше от 𝑙.
Перейдём из 𝑢 в него и продолжим по индукции.

Факт 2: отсутствие вырожденных вершин
Вершина вырожденная, если она и все её соседи попали на одну
прямую.
Факт 2. В «резиновой» укладке вырожденных вершин нет.

Пусть 𝑙 — прямая, соответствующая одной из вырожденных вершин.
Пусть 𝐷 — все вырожденные вершины, которым соответствует 𝑙.
Пусть 𝐻 — компонента связности в 𝐺 𝐷 .
Пусть 𝑉1 и 𝑉2 — вершины 𝐺 по разные стороны от 𝑙. По Факту 1, 𝐺 𝑉𝑖 связен.
По трёхсвязности 𝐺, найдутся различные вершины 𝑎, 𝑏, 𝑐 ∈ 𝐺 − 𝐻 ,
у каждой из которых есть сосед в 𝐻.
По определению, 𝑎, 𝑏, 𝑐 лежат на 𝑙, но имеют соседа вне 𝑙.
Тогда у каждой из вершин 𝑎, 𝑏, 𝑐 есть сосед как в 𝑉1, так и в 𝑉2.
Стянем 𝐺 𝑉1 к вершине 𝑣1, 𝐺 𝑉2 к 𝑣2 и 𝐻 к ℎ.
Вершины 𝑎, 𝑏, 𝑐, 𝑣1, 𝑣2, ℎ образовали 𝐾3,3 — противоречие.

Факт 3: разделённость гранных множеств
Факт 3.
Пусть 𝑎𝑏 — ребро 𝐺, и 𝐹1, 𝐹2 — два «гранных» множества рёбер,
содержащих 𝑎𝑏, и пусть 𝐹1, 𝐹2 ≠ Γ.
Пусть 𝑙 — прямая, проходящая через 𝑥 𝑎 и 𝑥 𝑏.
Тогда точки вершин 𝐹1 и 𝐹2 лежат по разные стороны от 𝑙.

Допустим, что нашлись вершины 𝑐 ∈ 𝐹1 и 𝑑 ∈ 𝐹2, такие, что 𝑥 𝑐 и 𝑥 𝑑
попали по «правую» сторону от 𝑙 либо на саму 𝑙.
Если 𝑥 𝑐 ∈ 𝑙, то у 𝑐 есть сосед, попавший по «правую» сторону от 𝑙.
(Аналогично для 𝑑.)
Согласно Факту 1, между 𝑐 и 𝑑 есть путь 𝑃𝑐𝑑, все вершины которого
лежат по правую сторону от 𝑙 (кроме, быть может, самих 𝑐 и 𝑑).
У 𝑎 и 𝑏 есть (по Факту 2) соседи по «левую» сторону от 𝑙.
Можно найти путь 𝑃𝑎𝑏 между 𝑎 и 𝑏, все вершины которого лежат
по левую сторону от 𝑙.
По построению, у путей 𝑃𝑎𝑏 и 𝑃𝑐𝑑 общих вершин не будет.

Допустим, что нашлись вершины 𝑐 ∈ 𝐹1 ∖ 𝑎, 𝑏 и 𝑑 ∈ 𝐹2 ∖ 𝑎, 𝑏 ,
такие, что 𝑥 𝑐 и 𝑥 𝑑 попали по «правую» сторону от 𝑙 либо на саму 𝑙.
Нашлись пути 𝑃𝑎𝑏 и 𝑃𝑐𝑑 без общих вершин.
Рассмотрим любую плоскую укладку 𝐺.
В этой укладке путь 𝑃𝑎𝑏 и само ребро 𝑎𝑏 отделяют вершину 𝑐 от 𝑑
— это противоречит существованию пути 𝑃𝑐𝑑.

«Гранные» множества переходят в
выпуклые многоугольники
Факт 3. Если 𝑎𝑏 — общее ребро «гранных» множеств 𝐹1, 𝐹2,
и 𝐹1, 𝐹2 ≠ Γ, то точки вершин 𝐹1 и 𝐹2 лежат по разные стороны
от прямой 𝑥 𝑎 𝑥 𝑏.
Из факта 3 следует, что любое «гранное» множество рёбер
переходит в выпуклый многоугольник (т.к. всегда лежит по одну
сторону от любого своего ребра).

У внутренностей многоугольников «гранных»
множеств (кроме Γ) нет общих точек
Факт 3. Если 𝑎𝑏 — общее ребро «гранных» множеств 𝐹1, 𝐹2, и 𝐹1, 𝐹2 ≠ Γ,
то точки вершин 𝐹1 и 𝐹2 лежат по разные стороны от прямой 𝑥 𝑎 𝑥 𝑏.
Пусть 𝑥 — произвольная точка внутри Γ.
Проведём через 𝑥 прямую 𝑙, не проходящую через вершины 𝐺
и возможные точки пересечения рёбер.
Будем двигаться по 𝑙 из бесконечности к 𝑥 и считать, сколько
многоугольников «гранных» множеств покрывают 𝑥.
Когда мы только заходим в Γ, такой многоугольник лишь один.
Когда мы пересекаем ребро, то уходим из одного многоугольника, входя
тут же в другой; т.е., по-прежнему, мы лишь в одном многоугольнике.

Рёбра в «резиновой» укладке
не пересекаются
«Гранные» множества переходят в выпуклые многоугольники.
У внутренностей многоугольников «гранных» множеств (кроме Γ)
нет общих точек.
Если бы у двух рёбер, не являющихся последовательными рёбрами
одной грани, была общая точка, то нашлись бы два гранных
множества, внутренности которых пересеклись — противоречие.
Теорема Татта доказана.

Существование «резиновой» укладки
Равновесие находим, исходя из законов Ньютона и Гука:
𝑓1 𝑓2
𝑓3
𝑓4
𝑓5 𝑖
𝑓𝑖 = 𝟎

Существование «резиновой» укладки
Пусть 𝑉 𝐺 = 𝑣1, … , 𝑣 𝑛 , и пусть координаты 𝑣1, … , 𝑣 𝑝 зафиксированы.
Пусть 𝑥𝑖, 𝑦𝑖 — координаты вершины 𝑣𝑖.
Условие равновесия:
∀𝑖 > 𝑝
𝑣 𝑖 𝑣 𝑗∈𝐸 𝐺
𝑥𝑗 − 𝑥𝑖, 𝑦𝑗 − 𝑦𝑖 = 0,0
Вектор координат 𝒙 = 𝑥 𝑝+1, … , 𝑥 𝑛 удовлетворяет системе вида
𝐴𝒙 = 𝒃,
где 𝐴 = 𝑎𝑖𝑗 , 𝑎𝑖𝑗 =
0 если 𝑖 ≠ 𝑗 и 𝑣𝑖 𝑣𝑗 ∉ 𝐸 𝐺
1 если 𝑣𝑖 𝑣𝑗 ∈ 𝐸 𝐺
− deg 𝑣𝑖 если 𝑖 = 𝑗

Что делать, если граф разрежен

Резиновая укладка непланарного графа

Резиновая укладка плотного графа

Метод Татта: плюсы и минусы
Плюсы:
• Достаточно быстрый
• Простая идея
• Математически обоснован
• Даёт симметричную укладку симметричных графов в случае
трёхсвязности
Минусы:
• Плохое разрешение
• Требуется трёхсвязность (дополнение до плотных графов
используется всего менее чем в 10% коммерческих пакетах)

Силовые методы укладки (force-directed)
Определяется система сил, действующих на укладку:
• Силы притяжения между вершинами
• Силы отталкивания между вершинами
• Силы, действующие на рёбра
Минимизируется «энергия» системы: стандартные численные
методы, моделирование отжига и пр.

Силовые методы укладки
Плюсы:
• Прозрачная идея и, как правило, простая реализация
• Возможность применять к разреженным графам
• Возможность применять к непланарным графам
• Возможность учесть самые разные эстетические требования
Минусы:
• Математически хорошо обоснован только метод Татта и очень
похожие
• Невысокая скорость при сложной функции энергии

�ݺ�ߣ

20140329 graph drawing_dainiak_lecture02

Recommended

More Related Content

What's hot (20)

Similar to 20140329 graph drawing_dainiak_lecture02 (15)

More from Computer Science Club (20)

20140329 graph drawing_dainiak_lecture02