4488
правок
Остовные деревья с низким растяжением: различия между версиями
Материал из WEGA
Остовные деревья с низким растяжением (посмотреть исходный код)
Версия от 12:14, 20 июля 2015
, 20 июля 2015→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
Среднее растяжение мультиграфа G = ( | Среднее растяжение мультиграфа <math>G = (V, E, \omega ) \; </math> определяется как наименьшее среднее растяжение остовного дерева T графа G – avestr(G, T). Среднее растяжение целого положительного числа n, avestr(n), представляет собой максимальное среднее растяжение n-вершинного мультиграфа G. Задача заключается в анализе асимптотического поведения функции avestr(n). | ||
Близкая (двойственная) задача заключается в построении вероятностного распределения D остовных деревьев для графа G, такого, что | Близкая (двойственная) задача заключается в построении вероятностного распределения D остовных деревьев для графа G, такого, что | ||
насколько возможно мало. Аналогично, expstr(G) = | |||
<math>expstr(G, D) = max_{e = (u, v) \in E} \mathbf{E}_{T \in D} (stretch_T(u, v))</math> | |||
насколько возможно мало. Аналогично, <math>expstr(G) = min_D \{ expstr(G, D) \} \;</math>, где минимум берется среди всех распределений D остовных деревьев графа G, и <math>expstr(n) = max_G \{ expstr(G) \} \; </math>, где максимум берется среди всех n-вершинных мультиграфов. | |||
