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

'''Евклидово минимальное остовное дерево''' (''Euclidean minimum spanning tree, EMST'') — это [[минимальное остовное дерево]] множества  из <math>n</math> точек на плоскости (или более обще, в <math>\R^d</math>, где <math>d \ge 2</math>), где вес ребра между любой парой точек является евклидовым расстоянием между ними. Другими словами, '''Евклидово минимальное остовное дерево''' соединяет отрезками некоторые пары заданного множества  из <math>n</math> точек так, что любая точка множества стала достижимой из любой другой точки множества по этим отрезкам, а общая длина всех отрезков была бы минимальна.

[[Категория: Обыкновенные графы‏‎]]