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

Для пары чисел <math>\alpha, \beta: \alpha \ge 1, \beta \ge 0 \;</math>, подграф <math>G' = (V, H) \;</math> невзвешенного неориентированного графа <math>G = (V, E), H \subseteq E \;</math>, является <math>(\alpha, \; \beta)</math>-остовом G, если для каждой пары вершин <math>u, w \in V \;</math> выполняется соотношение <math>dist_{G'} (u, w) \le \alpha \cdot dist_G (u, w) + \beta \;</math>, где <math>dist_G (u, w) \;</math> обозначает расстояние между u и w в G. Мы хотим показать, что для каждого n-вершинного графа существует разреженный <math>(\alpha, \; \beta)</math>-остов с настолько малыми значениями <math>\alpha \;a</math> и <math>\beta \;</math>, насколько это возможно. Задача заключается в нахождении асимптотического компромисса между <math>\alpha \;a</math> и <math>\beta \;</math>, с одной стороны, и разреженностью остова – с другой.