Остовные деревья с низким растяжением: различия между версиями

Перейти к навигации Перейти к поиску
Строка 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>
 


distT(u;v)
stretchT(u, v) = ——( u ; v distG(u, v)
and the average stretch over all edges of E is
stretchT(u, v) :
avestr(G; T) = 1
\E\
(u;v)2E
1    '


Среднее растяжение мультиграфа 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).
Источник — http://pco.iis.nsk.su/wega/index.php/Остовные_деревья_с_низким_растяжением