4551
правка
Ширина ленты графа: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
Файги доказал следующие положения. | Файги доказал следующие положения. | ||
''' | |||
Теорема 1. Существует эффективный алгоритм, который для графа <math>G = (V, E) \; </math> устанавливает линейный порядок <math>\pi : V \rightarrow \{ 1, 2, ..., n \}</math>, для которого <math>bw_{\pi } (G) \le O \Big( (log \; n)^3 \sqrt{log \; n \; log \; log \; n} \Big) \cdot D(G)</math>. В частности, имеется полилогарифмический относительно n | '''Теорема 1. Существует эффективный алгоритм, который для графа <math>G = (V, E) \; </math> устанавливает линейный порядок <math>\pi : V \rightarrow \{ 1, 2, ..., n \}</math>, для которого <math>bw_{\pi } (G) \le O \Big( (log \; n)^3 \sqrt{log \; n \; log \; log \; n} \Big) \cdot D(G)</math>. В частности, имеется полилогарифмический относительно n /poly(log n)/ алгоритм аппроксимации для решения задачи нахождения ширины ленты в графах общего вида.''' | ||
Алгоритмическую структуру Файги можно вкратце описать следующим образом. | Алгоритмическую структуру Файги можно вкратце описать следующим образом. | ||
1. Вычислить представление f: | 1. Вычислить представление <math>f: \rightarrow \mathbb{R}^n</math> графа G в евклидовом пространстве. | ||
2. Пусть ui,U2,..; un – независимые случайные переменные N(0, 1)1; для каждой вершины v 2 V вычислить h(v) = 1. N(0, 1) обозначает стандартную нормальную случайную переменную со средним значением 0 и отклонением 1. | 2. Пусть ui,U2,..; un – независимые случайные переменные N(0, 1)1; для каждой вершины v 2 V вычислить h(v) = 1. N(0, 1) обозначает стандартную нормальную случайную переменную со средним значением 0 и отклонением 1. | ||