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

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