Геометрические остовы: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 95: | Строка 95: | ||
Дас, Нарасимхан и Салоу [ ] доказали, что жадный остов удовлетворяет так называемому ''свойству прыжков''. Множество неориентированных ребер E удовлетворяет свойству t-прыжков, если для любого <math>k \ge 2 \;</math> и любой возможной последовательности | Дас, Нарасимхан и Салоу [11] доказали, что жадный остов удовлетворяет так называемому ''свойству прыжков''. Множество неориентированных ребер E удовлетворяет свойству t-прыжков, если для любого <math>k \ge 2 \;</math> и любой возможной последовательности <math>\{ (p_1, q_1), ..., (p_k, q_k) \} \;</math> попарно различающихся ребер E выполняется соотношение | ||
<math>t \cdot |p_1 q_1| < \sum^k_{i = 2} |p_i q_i| + t \cdot \Big( \sum^{k - 1}_{i = 1} |q_i p_{i + 1}| + |p_k q_1| \Big)</math>. | |||
Используя свойство прыжков, можно ограничить вес графа. Дас и Нарасимхан [ ] заметили, что жадный остов можно вычислить приближенно при удовлетворении свойства прыжков. Это наблюдение позволило разработать более быстрые алгоритмы для его построения. | |||
Используя свойство прыжков, можно ограничить вес графа. Дас и Нарасимхан [10] заметили, что жадный остов можно вычислить приближенно при удовлетворении свойства прыжков. Это наблюдение позволило разработать более быстрые алгоритмы для его построения. | |||