4551
правка
Ширина ленты графа: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 35: | Строка 35: | ||
Вложения с учетом объема | Вложения с учетом объема | ||
Осталось охарактеризовать только этап (1). Функция f должна каким-либо образом сохранять структуру графа G, чтобы алгоритм мог выдавать порядок с низкой шириной ленты. Существование такой функции f обуславливается наличием поля метрических вложений с малым уровнем искажений (см., например, [2, 14]). Файги предложил обобщение вложений с малым уровнем искажений до отображений, называемых вложениями с учетом объема. Грубо говоря, отображение f должно быть нерасширяющимся в том смысле, что | |||
Осталось охарактеризовать только этап (1). Функция f должна каким-либо образом сохранять структуру графа G, чтобы алгоритм мог выдавать порядок с низкой шириной ленты. Существование такой функции f обуславливается наличием поля метрических вложений с малым уровнем искажений (см., например, [2, 14]). Файги предложил обобщение вложений с малым уровнем искажений до отображений, называемых вложениями с учетом объема. Грубо говоря, отображение f должно быть нерасширяющимся в том смысле, что <math>\parallel f(u) — f(v) \parallel \le 1</math> для каждого ребра <math>\{ u, v \} \in E \;</math>, и должно обладать следующим свойством: для любого набора из k вершин <math>v_1, ..., v_k \;</math>, <math>(k-1) \;</math>-мерный объем выпуклой оболочки точек <math>f(v_1), ..., f(v_k) \;</math> должен быть максимально возможно большим. Для оптимизации эффективности алгоритма выбирается подходящее значение k. Точные определения вложений с учетом объема и детальное изложение их построения можно найти в работах [7, 10, 11]. Файге показал, что модификация алгоритма вложения Бургейна [2] дает отображение <math>f: \rightarrow \mathbb{R}^n</math>, достаточно хорошее для обеспечения справедливости теоремы 1. | |||