4446
правок
Остовные деревья с низким растяжением: различия между версиями
Материал из WEGA
Остовные деревья с низким растяжением (посмотреть исходный код)
Версия от 11:58, 20 июля 2015
, 20 июля 2015→Постановка задачи
Irina (обсуждение | вклад) м (→См. также) |
Irina (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассмотрим взвешенный связный мультиграф G = (V, E, omega), где omega – функция, отображающая множество ребер E графа G на множество положительных вещественных чисел. Вес пути P в графе P равен сумме весов ребер, входящих в этот путь. Для пары вершин u, v | Рассмотрим взвешенный связный мультиграф <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> определяется следующим образом: | ||
distT(u;v) | distT(u;v) | ||
| Строка 27: | Строка 27: | ||
Рассматривая задачу как игру двух игроков с нулевой суммой, где игрок «дерево» стремится минимизировать выигрыш, а игрок «ребро» – максимизировать его, легко увидеть, что для любого целого положительного числа n avestr(n) = expstr(n) [2]. Однако вероятностная версия задачи оказывается намного более удобной для многих вариантов приложений. | Рассматривая задачу как игру двух игроков с нулевой суммой, где игрок «дерево» стремится минимизировать выигрыш, а игрок «ребро» – максимизировать его, легко увидеть, что для любого целого положительного числа n avestr(n) = expstr(n) [2]. Однако вероятностная версия задачи оказывается намного более удобной для многих вариантов приложений. | ||
== Основные результаты == | == Основные результаты == | ||
