Геом Поиск Локализация

трапеций (Зайделя) позже

подразбиение плоскости
Представление ППЛГ. Реберный список с двойными связями
Метод цепей (продолжение)
Метод

детализации триангуляции

плоскости
Граф G = (V, E) называется планарным, если его можно

уложить на плоскости без самопересечений.
Планарное подразбиение или карта порождается прямолинейной укладкой ребер планарного графа на плоскости.

V = { v1, v2, …, vn } – вершины,
E = { e1, e2, …, em } – ребра,
{ f1, f2, …, fl } – грани,
n – число вершин,
m – число ребер,
l – число граней

n = 5 m = 6
l = 3
5 + 3 = 6 + 2

f2

f1

f3

f2

f1

n = 6 m = 6
l = 2
6 + 2 = 6 + 2

f1

n = 5 m = 4
l = 1
5 + 1 = 4 + 2

Формула Эйлера:
n + l = m + 2

m + 2
G – связный плоский граф. T – его

остовное дерево.
В дереве m = n – 1, l = 1 и т. о. n + 1 = (n – 1) + 2.
Не изменяя n, добавляем к остову ребро → образуется грань,
т. е. m → m + 1, l → l + 1 и формула остается верной.
Повторяем эту операцию. При этом формула Эйлера есть инвариант и останется верной после завершения таких шагов и получения графа G. ♦
Стереографическая проекция

многограннике n + l = m + 2
Следствие 2а:
Для связного

планарного графа m ≤ 3n – 6 при n ≥ 3.

Формула Эйлера: n + l = m + 2

(т.к. граф без петель и параллельных ребер)
Т.о. 2m ≥ 3l .
l = m + 2 – n → 2m ≥ 3(m + 2 – n ) → m ≤ 3n – 6 ♦

d (fi) – степень грани (число ребер границы, мосты – дважды)

l ≤ 2n – 4 при n ≥ 3.
Следствие

3: Графы K5 и K3,3 не планарны.

Формула Эйлера: n + l = m + 2

– треугольники.
Триангуляция множества точек – триангуляция выпуклой оболочки.
Плоская триангуляция:

связный плоский граф, каждая грань которого (в том числе и внешняя) – треугольник.
В этом случае m = 3n – 6 и l = 2n – 4

n = 3
m = 3
l = 2

n := n + 1
m := m + 3
l := l + 2

n := n + 1
m := m + 3
l := l + 2

n := n + 1
m := m + 2
l := l + 1

связями (РСДС)
Основная компонента (элемент списка) РСДС – реберный узел

v6

f2

v5

v4

v3

v2

v1

f1

p2

p1

ek

связями (РСДС)
e1












e6
e7
e4
e5
e2
e3
v4
v3
v1
v5
f4
f3
f2
f1
v2

по граням head_F [1..l]
Представление ППЛГ Реберный список с

двойными связями (РСДС)

связями (РСДС)
Процедура «Инцидентные ребра»
(см. файл MS Word «РеберныйСписокДС»)

связями (РСДС)
Процедура «Граница грани» (см. файл MS Word «РеберныйСписокДС»)

Cr } называется
полным множеством монотонных цепей графа, если:
Метод

цепей (продолжение)

2. Для ∀ i, j ∈1..r (I ≠ j): те узлы из Ci ,, которые не являются узлами Cj,, лежат по одну сторону от Cj,.

«Локализация точки» (п.1.3) в папке «Лекция 5»

позже
Конец лекции