4551
правка
Ширина ленты графа: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача нахождения ширины ленты графа заключается в установлении линейного порядка над вершинами графа G = (V, E), позволяющего минимизировать максимальное «растяжение» любого ребра в этом упорядочении. Более формально, пусть n = |V|. Рассмотрим отображение «сколько угодно к одному»: V | Задача нахождения ширины ленты графа заключается в установлении линейного порядка над вершинами графа G = (V, E), позволяющего минимизировать максимальное «растяжение» любого ребра в этом упорядочении. Более формально, пусть n = |V|. Рассмотрим отображение «сколько угодно к одному» <math>\pi : V \rightarrow \{ 1, 2, ..., n \}</math>. Ширина этого упорядочения составляет bw^(G) = maxfu;vg2Ej \л{и) — JI{V)\. Ширина ленты графа G задается шириной ленты лучшего возможного упорядочения: bw(G) = min^ bw^(G). | ||
| Строка 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), но до выхода основополагающей работы Файги [ ] оно оставалось недоказанным. | Обозначим для любой пары вершин 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), но до выхода основополагающей работы Файги [ ] оно оставалось недоказанным. | ||
== Основные результаты == | == Основные результаты == | ||