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

Среднее растяжение мультиграфа <math>G = (V, E, \omega ) \; </math> определяется как наименьшее среднее растяжение остовного дерева T графа G – avestr(G, T). Среднее растяжение целого положительного числа n, avestr(n), представляет собой максимальное среднее растяжение n-вершинного мультиграфа G. Задача заключается в анализе асимптотического поведения функции avestr(n).

 

 

 

насколько возможно мало. Аналогично, <math>expstr(G) = min_D \{ expstr(G, D) \} \;</math>, где минимум берется среди всех распределений D остовных деревьев графа G, и <math>expstr(n) = max_G \{ expstr(G) \} \; </math>, где максимум берется среди всех n-вершинных мультиграфов.