Аноним

Ширина ленты графа: различия между версиями

Материал из WEGA
Строка 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; v 2 V за d(u,v) кратчайшее расстояние между u и v в графе G. Затем определим B(v, r) = fu 2 V : d(u;v) < rg как шар радиуса r вокруг вершины v 2 V. Наконец, определим локальную плотность G как D(G) = maxveV,r>i jB(v, r)j/(2r): Нетрудно заметить, что bw(G) > D(G). Было высказано предположение, что существует верхняя граница вида bw(G) < poly(log n) ■ D(G), но до выхода основополагающей работы Файги [ ] оно оставалось недоказанным.
 
Обозначим для любой пары вершин <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), но до выхода основополагающей работы Файги [ ] оно оставалось недоказанным.


== Основные результаты ==
== Основные результаты ==
4551

правка