Аноним

Ширина ленты графа: различия между версиями

Материал из WEGA
Строка 29: Строка 29:
N(0, 1) обозначает стандартную нормальную случайную переменную со средним значением 0 и отклонением 1.
N(0, 1) обозначает стандартную нормальную случайную переменную со средним значением 0 и отклонением 1.


3. Отсортировать вершины по значению h(v), разрывая связи произвольным образом, и выдать порожденный линейный порядок. Эквивалентная характеризация этапов (2) и (3) необходима для выбора равномерного случайного вектора a 2 S""1 из (n-1)-мерной сферы Sn~1 С Rn и выдачи линейного порядка, порожденного значениями h(v) = ha;f(v)i, где (•,•) обозначает обычное скалярное произведение над Rn. Иными словами, вначале алгоритм вычисляет карту f: V ! Rn, проецирует изображения вершин на произвольно ориентированную линию и затем выдает порожденный в результате линейный порядок; этап (2) представляет собой стандартный способ реализации подобной случайной проекции.
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) представляет собой стандартный способ реализации подобной случайной проекции.




4551

правка