4551
правка
Остовные деревья с низким растяжением: различия между версиями
Материал из WEGA
Остовные деревья с низким растяжением (посмотреть исходный код)
Версия от 12:07, 20 июля 2015
, 20 июля 2015→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассмотрим взвешенный связный мультиграф <math>G = (V, E, \omega ) \; </math>, где <math>\omega \;</math> – функция, отображающая множество ребер E графа G на множество положительных вещественных чисел. Вес пути P в графе P равен сумме весов ребер, входящих в этот путь. Для пары вершин <math>u, v \in V \;</math> за расстояние между ними в графе G принимается минимальный вес пути, соединяющего u и v в G. Для остовного дерева T графа G растяжение дуги <math>(u, v) \in E \;</math> определяется следующим образом: | Рассмотрим взвешенный связный мультиграф <math>G = (V, E, \omega ) \; </math>, где <math>\omega \;</math> – функция, отображающая множество ребер E графа G на множество положительных вещественных чисел. Вес пути P в графе P равен сумме весов ребер, входящих в этот путь. Для пары вершин <math>u, v \in V \;</math> за расстояние между ними в графе G принимается минимальный вес пути, соединяющего u и v в G. Для остовного дерева T графа G [[растяжение]] дуги <math>(u, v) \in E \;</math> определяется следующим образом: | ||
<math>stretch_T(u, v) = \frac{dist_T(u, v)}{dist_G(u, v)} | |||
</math> | |||
а среднее растяжение по всем дугам E составляет | |||
<math>avestr(G, T) = \frac{1}{|E|} \sum_{(u, v) \in E} stretch_T(u, v).</math> | |||
Среднее растяжение мультиграфа G = (v, E, omega) определяется как наименьшее среднее растяжение остовного дерева tree T графа G – avestr(G; T). Среднее растяжение целого положительного числа n, avestr(n), представляет собой максимальное среднее растяжение n-вершинного мультиграфа G. Задача заключается в анализе асимптотического поведения функции avestr(n). | Среднее растяжение мультиграфа G = (v, E, omega) определяется как наименьшее среднее растяжение остовного дерева tree T графа G – avestr(G; T). Среднее растяжение целого положительного числа n, avestr(n), представляет собой максимальное среднее растяжение n-вершинного мультиграфа G. Задача заключается в анализе асимптотического поведения функции avestr(n). | ||
