4551
правка
Минимальные геометрические остовные деревья: различия между версиями
Перейти к навигации
Перейти к поиску
Минимальные геометрические остовные деревья (посмотреть исходный код)
Версия от 00:50, 19 декабря 2015
, 19 декабря 2015→Постановка задачи
Irina (обсуждение | вклад) м (→См. также) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть S – множество из n точек в d-мерном вещественном пространстве, где d – целочисленная константа | Пусть S – множество из n точек в d-мерном вещественном пространстве, где <math>d \ge 1 \;</math> – целочисленная константа. [[Минимальное остовное дерево]] (MST) графа S представляет собой связный ациклический граф с множеством вершин S и минимальной суммарной длиной ребер. Длина ребра равна расстоянию между его конечными точками согласно некоторой метрике. В метрике <math>L_p \;</math> расстояние между двумя точками x и y с координатами <math>(x_1, x_2, ..., x_d) \;</math> и <math>(y_1, y_2, ..., yd_) \;</math>, соответственно, определяется как p-й корень суммы <math>\sum^d_{i=1} |x_i - y_i|^p \;</math>. | ||
== Основные результаты == | == Основные результаты == | ||