4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Для пары чисел <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 \; | Для пары чисел <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 \;</math> и <math>\beta \;</math>, насколько это возможно. Задача заключается в нахождении асимптотического компромисса между <math>\alpha \;</math> и <math>\beta \;</math>, с одной стороны, и разреженностью остова – с другой. | ||
== Основные результаты == | == Основные результаты == |
правка