Пусть известна структура сети. Если в дереве оставить только D-точки и инцидентные им ребра, то дерево разобьется на компоненты связности, причем D-точки связаны между собой, если они лежат в одной компоненте. Вернув в каждую компоненту инцидентные ее вершинам ребра и их концы – основные точки, мы получим компоненты Штейнера (КШ). Невисячие вершины КШ –D-точки Þ все внутренние углы КШ = 120°. Число D-точек в компоненте с k вершинами = k-2, число ребер =k+(k-2)-1=2k-3.
При замене пары соседних по структуре точек А и В на В´ число основных и дополнительных вершин уменьшается на 1, а длина сети остается неизменной (сумма трех отрезков АО, ВО и СО равна длине отрезка В´С). Уменьшив число вершин до двух, получим отрезок с базовым направлением b и длиной = длине сети с заданной структурой (исп. при сравнении вариантов структур)
Направления b + dk отрезков сети имеют 3 типа, т.е. dk Î{0, +60°, -60°}. После нахождения направлений повторяем вычисления, заменяя построение ∆ABВ ́ на ∆ABO Для этого из вершин А и В проводим лучи с направлениями b + dk Þ находим вершину О (на рис. ставим номер на ∆-к).
При проходке 1 определяем смещения dk , затем базу b, а при проходке 2 – сами D-точки.
Пример. k =5, r=2 ´5 -3 =7
Нерекурсивный алгоритм нахождения координат D-точек при заданной структуре.
0) Выделить компоненты Штейнера и для каждой компоненты выполнить:
1) Расставить пометки типов направлений на ребрах КШ (3типа).
2) Построить последовательность треугольников наружу с углами 60°.
3) Получить базовый отрезок с базовым направлением и длиной сети.
4) Построить последовательность треугольников внутрь с известными углами.
Заметим, что искать надо не только координаты D-точек, но и структуру сети. Число различных структур конечно, но с ростом nрастет по экспоненте Þ для поиска структуры применяют эвристические алгоритмы.Мы будем строить МОД и для вершин углов, меньших 120°, решать задачу Зейделя.
S2= (3/2)2 + (√3/2)2 = 3
Алгоритм с выбором структуры: а) Находим и удаляем наиболее далекую в Х вершину х (удаление которой максимально уменьшает диаметр Х).
б) Рекурсивно строим дерево Штейнера на n-1 вершинах (м.б. неоднозначно).
в) Цепляем точку х к дереву через одного из ее соседей по Вороному.
г) Если угол < 120°, то внутри угла ставим дополнительную точку и соединяем ее с тремя вершинами угла, а старые стороны угла удаляем.
Рекурсивный алгоритм нахождения координат D-точек по заданной структуре сети.
Пусть V – множество вершин, n – их количество.
1. Если n £ 3 – решение тривиально.
2. Выбираем пару соседних по структуре точек a и b.
3. Строим правильный треугольник на стороне ab и обозначаем вершину c.
4. Решаем рекурсивно задачу на множестве точек .
5. Решаем задачу для треугольника (a,b,d), где d – точка, связанная с точкой c в структуре, полученной на шаге 4.
Пример. Заменив точки 1 и 2 на точку 12, а точки 4 и 5 на точку 45, решаем последовательно задачи: B=Z3(12,3,45), A=Z3(1,2,B) и C=Z3(B,4,5). Процесс построения запишем условно с помощью операций + (строим правильный треугольник), – (проводим отрезок), ´ (пересекаем прямые):
1) 1 + 2 = 12 5) 12 – 345 = La 9) 1 + B = 1B 13) B + 4 = B4
2) 4 + 5 = 45 6) 123 – 45 = Lc 10) 2 – 1B = L2 14) B4 – 5 = L5
3) 12 + 3 =123 7) La ´ Lc = B 11) La ´ L2 = A 15) Lc ´ L5 = C
4) 3 + 45 = 345 8) 3 – B = L3 12) A – 1 = L1 16) C – 4 = L4
№5. ДИАГРАММА ВОРОНОГО И ГРАФ ДЕЛОНЕ.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.