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

(Евклидова) задача нахождения k-вершинно-связной остовной сети минимальной стоимости

Для заданного множества S из n точек в евклидовом пространстве Rd найти k-вершинно-связную сеть минимальной стоимости, охватывающую все точки S.

(Евклидова) задача нахождения k-реберно-связной остовной сети минимальной стоимости

Для заданного множества S из n точек в евклидовом пространстве Rd найти k-реберно-связную евклидову сеть минимальной стоимости, охватывающую все точки S. Рассматривается также вариант, допускающий наличие параллельных ребер:

(Евклидова) задача нахождения k-реберно-связной остовной мультисети минимальной стоимости

Для заданного множества S из n точек в евклидовом пространстве Rd найти k-реберно-связную евклидову сеть минимальной стоимости, охватывающую точки S (в случае мультисети она может содержать параллельные ребра).