4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача нахождения ширины ленты графа заключается в установлении линейного порядка над вершинами графа <math>G = (V, E) \; </math>, позволяющего минимизировать максимальное «растяжение» любого ребра в этом упорядочении. Более формально, пусть <math>n = |V| \; </math>. Рассмотрим любое взаимно-однозначное отображение <math>\pi : V \rightarrow \{ 1, 2, ..., n \}</math>. Ширина этого упорядочения составляет <math>bw_{\pi } (G) = max_{ \{ u, v \} \in E} | \pi (u) - \pi (v) | </math>. Ширина ленты графа G задается шириной ленты лучшего возможного упорядочения: <math>bw(G) = min_{\pi } bw_{\pi }(G) \; </math>. | Задача нахождения ширины ленты графа заключается в установлении линейного порядка над вершинами графа <math>G = (V, E) \;</math>, позволяющего минимизировать максимальное «растяжение» любого ребра в этом упорядочении. Более формально, пусть <math>n = |V| \;</math>. Рассмотрим любое взаимно-однозначное отображение <math>\pi : V \rightarrow \{ 1, 2, ..., n \}</math>. Ширина этого упорядочения составляет <math>bw_{\pi } (G) = max_{ \{ u, v \} \in E} | \pi (u) - \pi (v) | </math>. Ширина ленты графа G задается шириной ленты лучшего возможного упорядочения: <math>bw(G) = min_{\pi } bw_{\pi }(G) \; </math>. | ||
Строка 12: | Строка 12: | ||
Локальная плотность | Локальная плотность | ||
Обозначим для любой пары вершин u | |||
Обозначим для любой пары вершин <math>u, v \in V \;</math> за <math>d(u,v) \;</math> кратчайшее расстояние между u и v в графе G. Затем определим <math>B(v, r) = \{ u \in V : d(u, v) \le r \}</math> как шар радиуса r вокруг вершины <math>v \in V \;</math>. Наконец, определим локальную плотность G как D(G) = maxveV,r>i jB(v, r)j/(2r): Нетрудно заметить, что bw(G) > D(G). Было высказано предположение, что существует верхняя граница вида bw(G) < poly(log n) ■ D(G), но до выхода основополагающей работы Файги [ ] оно оставалось недоказанным. | |||
== Основные результаты == | == Основные результаты == |
правка