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

Обозначим для любой пары вершин <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 как <math>D(G) = max_{v \in V, r \ge 1} | B(v, r) | / (2r)</math>. Нетрудно заметить, что <math>bw(G) \ge D(G) \;</math>. Было высказано предположение, что существует верхняя граница вида <math>bw(G) \le poly(log \; n) \cdot D(G)</math>, но до выхода основополагающей работы Файги [7] оно оставалось недоказанным.