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

Задача нахождения ширины ленты графа заключается в установлении линейного порядка над вершинами графа <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>.

Обозначим для любой пары вершин 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), но до выхода основополагающей работы Файги [ ] оно оставалось недоказанным.