4551
правка
Ширина ленты графа: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 31: | Строка 31: | ||
3. Отсортировать вершины по значению h(v), разрывая связи произвольным образом, и выдать порожденный линейный порядок. | 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>. Иными словами, вначале алгоритм вычисляет | Эквивалентная характеризация этапов (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>. Иными словами, вначале алгоритм вычисляет отображение <math>f: \rightarrow \mathbb{R}^n</math>, проецирует изображения вершин на произвольно ориентированную линию и затем выдает порожденный в результате линейный порядок; этап (2) представляет собой стандартный способ реализации подобной случайной проекции. | ||