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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «== Ключевые слова и синонимы == Геометрические графы; евклидовы графы == Постановка задачи…»)
(нет различий)

Версия от 12:59, 6 сентября 2016

Ключевые слова и синонимы

Геометрические графы; евклидовы графы

Постановка задачи

Рассматривается следующая классическая задача оптимизации: для заданной неориентированной взвешенной геометрической сети найти подсеть минимальной стоимости, удовлетворяющую заданным априори требованиям многосвязности.

Нотация

Пусть G = (V, E) – геометрическая сеть, множество вершин V которой соответствует множеству из n точек в R d для определенного целого числа d > 2, а множество ребер E – множеству прямолинейных сегментов, соединяющих пары точек из V. Сеть G называется полной, если E соединяет все пары точек из V.