4551
правка
Ширина ленты графа: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 29: | Строка 29: | ||
N(0, 1) обозначает стандартную нормальную случайную переменную со средним значением 0 и отклонением 1. | N(0, 1) обозначает стандартную нормальную случайную переменную со средним значением 0 и отклонением 1. | ||
3. Отсортировать вершины по значению h(v), разрывая связи произвольным образом, и выдать порожденный линейный порядок. Эквивалентная характеризация этапов (2) и (3) необходима для выбора равномерного случайного вектора a | 3. Отсортировать вершины по значению h(v), разрывая связи произвольным образом, и выдать порожденный линейный порядок. | ||
Эквивалентная характеризация этапов (2) и (3) необходима для выбора равномерного случайного вектора <math>a \in S^{n-1}</math> из (n-1)-мерной сферы <math>S^{n-1} \subset \mathbb{R}^n</math> и выдачи линейного порядка, порожденного значениями <math>h(v) = \big\langle a, f(v) \big\rangle </math>, где <math>\big\langle \cdot , \cdot \big\rangle </math> обозначает обычное скалярное произведение над <math>\mathbb{R}^n</math>. Иными словами, вначале алгоритм вычисляет карту f: V ! Rn, проецирует изображения вершин на произвольно ориентированную линию и затем выдает порожденный в результате линейный порядок; этап (2) представляет собой стандартный способ реализации подобной случайной проекции. | |||