4551
правка
Планарные остовы ограниченной степени с малыми весами: различия между версиями
Перейти к навигации
Перейти к поиску
Планарные остовы ограниченной степени с малыми весами (посмотреть исходный код)
Версия от 15:05, 19 сентября 2013
, 19 сентября 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
'''Лемма 1. Граф <math>S \Theta\ GG</math> является связным, если лежащий в его основе граф <math>GG \;</math> является связным. Более того, для любых двух вершин u и v существует путь <math>\{ u, t_1, ... , t_r, v \} \; </math>, соединяющий их, такой, что все его дуги имеют длину менее <math>\sqrt{2} \big\| uv \big\| </math>.''' | '''Лемма 1. Граф <math>S \Theta\ GG</math> является связным, если лежащий в его основе граф <math>GG \;</math> является связным. Более того, для любых двух вершин u и v существует путь <math>\{ u, t_1, ... , t_r, v \} \; </math>, соединяющий их, такой, что все его дуги имеют длину менее <math>\sqrt{2} \big\| uv \big\| </math>.''' | ||
'''Теорема 2. Структура S | '''Теорема 2. Структура <math>S \Theta\ GG</math> состоит из узлов степенью не выше k – 1 и представляет собой сильный планарный остов с <math>\Theta\ </math>-разделенными соседями. Его коэффициент растяжения по мощности не превышает <math>\rho\ = \sqrt{2}^\beta\ / (1 - (2 \sqrt{2} sin \frac{ \pi\ }{k} )^\beta\ )</math>, где <math>k \ge 9</math> – настраиваемый параметр.''' | ||
Очевидно, что для двух конечных точек каждой дуги эта конструкция является согласованной: если дуга uv принадлежит к узлу u, то она точно также принадлежит и к узлу v. Стоит отметить, что число 3 в критерии \\xy\\ > тах(||ку||, 3||мх||, 3||vy||) было выбрано со всей тщательностью. | Очевидно, что для двух конечных точек каждой дуги эта конструкция является согласованной: если дуга uv принадлежит к узлу u, то она точно также принадлежит и к узлу v. Стоит отметить, что число 3 в критерии \\xy\\ > тах(||ку||, 3||мх||, 3||vy||) было выбрано со всей тщательностью. | ||