Планарные остовы ограниченной степени с малыми весами: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
'''Определение 1 ( | '''Определение 1 ( <math>\Theta\ </math>-доминирующая область)'''. Для каждого соседа v узла u <math>\Theta\ </math>-доминирующей областью v является <math>2 \Theta\ </math>-конус с вершиной в u, осью которого является дуга uv. | ||
Пусть NUDG(U) – множество соседей узла u в UDG. Пусть N(u) – множество соседей узла u в финальной топологии, которая была инициализирована как множество соседних узлов в GG. | Пусть NUDG(U) – множество соседей узла u в UDG. Пусть N(u) – множество соседей узла u в финальной топологии, которая была инициализирована как множество соседних узлов в GG. | ||
Алгоритм 1 строит сильный планарный остов степени (k – 1). | Алгоритм 1 строит сильный планарный остов степени (k – 1). | ||