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

Сентябрь 3, 2022

Главная
Алгебра
Геом Поиск Локализация

Содержание

2. 06.04.2007 Геометрический поиск Локализация точки 2 Геометрический поиск Планарные графы. Планарное прямолинейное подразбиение плоскости Представление ППЛГ.
3. 06.04.2007 Геометрический поиск Локализация точки 2 Геометрический поиск Планарные графы Планарное прямолинейное подразбиение плоскости Граф G
4. 06.04.2007 Геометрический поиск Локализация точки 2 Формула Эйлера: n + l = m + 2 G
5. 06.04.2007 Геометрический поиск Локализация точки 2 Стереографическая проекция v v′ N
6. 06.04.2007 Геометрический поиск Локализация точки 2 Следствие 1: Во всяком выпуклом многограннике n + l =
7. 06.04.2007 Геометрический поиск Локализация точки 2 Следствие 2б: Для связного планарного графа l ≤ 2n –
8. 06.04.2007 Геометрический поиск Локализация точки 2 Плоские триангуляции Триангуляция: все конечные грани – треугольники. Триангуляция множества
9. 06.04.2007 Геометрический поиск Локализация точки 2 Представление ППЛГ Реберный список с двойными связями (РСДС) Основная компонента
10. 06.04.2007 Геометрический поиск Локализация точки 2 Представление ППЛГ Реберный список с двойными связями (РСДС) e1 e6
11. 06.04.2007 Геометрический поиск Локализация точки 2 массивы входов: по вершинам head_V [1..n] по граням head_F [1..l]
12. 06.04.2007 Геометрический поиск Локализация точки 2 Представление ППЛГ Реберный список с двойными связями (РСДС) Процедура «Инцидентные
13. 06.04.2007 Геометрический поиск Локализация точки 2 Представление ППЛГ Реберный список с двойными связями (РСДС) Процедура «Граница
14. 06.04.2007 Геометрический поиск Локализация точки 2 Множество C = {C1, …, Cr } называется полным множеством
15. 06.04.2007 Геометрический поиск Локализация точки 2 Построение ПММЦ Балансировка весов ребер 1 1 1 1 1
16. 06.04.2007 Геометрический поиск Локализация точки 2 Регуляризация графа Метод заметания
17. 06.04.2007 Геометрический поиск Локализация точки 2 Метод детализации триангуляции См. Документ MWord «Локализация точки» (п.1.3) в
19. Скачать презентацию

Слайд 2

06.04.2007
Геометрический поиск Локализация точки 2
Геометрический поиск
Планарные графы. Планарное прямолинейное подразбиение плоскости
Представление

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

Слайд 3

06.04.2007
Геометрический поиск Локализация точки 2
Геометрический поиск
Планарные графы
Планарное прямолинейное подразбиение плоскости
Граф 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

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

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

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

Слайд 4

06.04.2007
Геометрический поиск Локализация точки 2
Формула Эйлера: n + l = m +

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

Слайд 5

06.04.2007
Геометрический поиск Локализация точки 2
Стереографическая проекция
v
v′
N

Слайд 6

06.04.2007
Геометрический поиск Локализация точки 2
Следствие 1:
Во всяком выпуклом многограннике 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) – степень грани (число ребер границы, мосты – дважды)

Слайд 7

06.04.2007
Геометрический поиск Локализация точки 2
Следствие 2б:
Для связного планарного графа l ≤

2n – 4 при n ≥ 3.
Следствие 3: Графы K5 и K3,3 не планарны.

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

Слайд 8

06.04.2007
Геометрический поиск Локализация точки 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 + 2
l := l + 1

Слайд 9

06.04.2007
Геометрический поиск Локализация точки 2
Представление ППЛГ Реберный список с двойными связями (РСДС)

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

Слайд 10

06.04.2007
Геометрический поиск Локализация точки 2
Представление ППЛГ Реберный список с двойными связями (РСДС)

Слайд 11

06.04.2007
Геометрический поиск Локализация точки 2
массивы входов:
по вершинам head_V [1..n]
по граням

head_F [1..l]

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

Слайд 12

06.04.2007
Геометрический поиск Локализация точки 2
Представление ППЛГ Реберный список с двойными связями (РСДС)

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

Слайд 13

06.04.2007
Геометрический поиск Локализация точки 2
Представление ППЛГ Реберный список с двойными связями (РСДС)

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

Слайд 14

06.04.2007
Геометрический поиск Локализация точки 2
Множество C = {C1, …, Cr }

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

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

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

Слайд 15

06.04.2007
Геометрический поиск Локализация точки 2
Построение ПММЦ Балансировка весов ребер
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
3
1
2
2
1

Слайд 16

06.04.2007
Геометрический поиск Локализация точки 2
Регуляризация графа Метод заметания

Слайд 17

06.04.2007
Геометрический поиск Локализация точки 2
Метод детализации триангуляции
См. Документ MWord «Локализация точки»

(п.1.3) в папке «Лекция 5»

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

Содержание

06.04.2007Геометрический поиск Локализация точки 2Геометрический поискПланарные графы. Планарное прямолинейное подразбиение плоскостиПредставление

06.04.2007Геометрический поиск Локализация точки 2Геометрический поискПланарные графыПланарное прямолинейное подразбиение плоскостиГраф G

06.04.2007Геометрический поиск Локализация точки 2Формула Эйлера: n + l = m +

06.04.2007Геометрический поиск Локализация точки 2Стереографическая проекцияvv′N

06.04.2007Геометрический поиск Локализация точки 2Следствие 1: Во всяком выпуклом многограннике n

06.04.2007Геометрический поиск Локализация точки 2Следствие 2б:Для связного планарного графа l ≤

06.04.2007Геометрический поиск Локализация точки 2Плоские триангуляцииТриангуляция: все конечные грани – треугольники.Триангуляция

06.04.2007Геометрический поиск Локализация точки 2Представление ППЛГ Реберный список с двойными связями (РСДС)

06.04.2007Геометрический поиск Локализация точки 2Представление ППЛГ Реберный список с двойными связями (РСДС)

06.04.2007Геометрический поиск Локализация точки 2массивы входов:по вершинам head_V [1..n] по граням

06.04.2007Геометрический поиск Локализация точки 2Представление ППЛГ Реберный список с двойными связями (РСДС)

06.04.2007Геометрический поиск Локализация точки 2Представление ППЛГ Реберный список с двойными связями (РСДС)

06.04.2007Геометрический поиск Локализация точки 2Множество C = {C1, …, Cr }

06.04.2007Геометрический поиск Локализация точки 2Построение ПММЦ Балансировка весов ребер1111111112111111131221

06.04.2007Геометрический поиск Локализация точки 2Регуляризация графа Метод заметания

06.04.2007Геометрический поиск Локализация точки 2Метод детализации триангуляцииСм. Документ MWord «Локализация точки»

Похожие презентации

06.04.2007
Геометрический поиск Локализация точки 2
Геометрический поиск
Планарные графы. Планарное прямолинейное подразбиение плоскости
Представление

06.04.2007
Геометрический поиск Локализация точки 2
Геометрический поиск
Планарные графы
Планарное прямолинейное подразбиение плоскости
Граф G

06.04.2007
Геометрический поиск Локализация точки 2
Формула Эйлера: n + l = m +

06.04.2007
Геометрический поиск Локализация точки 2
Стереографическая проекция
v
v′
N

06.04.2007
Геометрический поиск Локализация точки 2
Следствие 1:
Во всяком выпуклом многограннике n

06.04.2007
Геометрический поиск Локализация точки 2
Следствие 2б:
Для связного планарного графа l ≤

06.04.2007
Геометрический поиск Локализация точки 2
Плоские триангуляции
Триангуляция: все конечные грани – треугольники.
Триангуляция

06.04.2007
Геометрический поиск Локализация точки 2
Представление ППЛГ Реберный список с двойными связями (РСДС)

06.04.2007
Геометрический поиск Локализация точки 2
Представление ППЛГ Реберный список с двойными связями (РСДС)

06.04.2007
Геометрический поиск Локализация точки 2
массивы входов:
по вершинам head_V [1..n]
по граням

06.04.2007
Геометрический поиск Локализация точки 2
Представление ППЛГ Реберный список с двойными связями (РСДС)

06.04.2007
Геометрический поиск Локализация точки 2
Представление ППЛГ Реберный список с двойными связями (РСДС)

06.04.2007
Геометрический поиск Локализация точки 2
Множество C = {C1, …, Cr }

06.04.2007
Геометрический поиск Локализация точки 2
Построение ПММЦ Балансировка весов ребер
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
3
1
2
2
1

06.04.2007
Геометрический поиск Локализация точки 2
Регуляризация графа Метод заметания

06.04.2007
Геометрический поиск Локализация точки 2
Метод детализации триангуляции
См. Документ MWord «Локализация точки»