4551
правка
Ширина ленты графа: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
1. Вычислить представление <math>f: \rightarrow \mathbb{R}^n</math> графа G в евклидовом пространстве. | 1. Вычислить представление <math>f: \rightarrow \mathbb{R}^n</math> графа G в евклидовом пространстве. | ||
2. Пусть | 2. Пусть <math>u_1, u_2, ..., u_n \; </math> – независимые случайные переменные N(0, 1); для каждой вершины <math>v \in V \; </math> вычислить <math>h(v) = \sum_{i=1}^n u_i f_i(v)</math>, где <math>f_i(v) \; </math> – i-я координата вектора <math>f(v) \;</math>. | ||
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) необходима для выбора равномерного случайного вектора a 2 S""1 из (n-1)-мерной сферы Sn~1 С Rn и выдачи линейного порядка, порожденного значениями h(v) = ha;f(v)i, где (•,•) обозначает обычное скалярное произведение над Rn. Иными словами, вначале алгоритм вычисляет карту f: V ! Rn, проецирует изображения вершин на произвольно ориентированную линию и затем выдает порожденный в результате линейный порядок; этап (2) представляет собой стандартный способ реализации подобной случайной проекции. | ||