Минимальные k-связные геометрические сети: различия между версиями
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Геометрические графы; евклидовы графы == Постановка задачи…») |
Irina (обсуждение | вклад) |
||
| Строка 7: | Строка 7: | ||
== Нотация == | == Нотация == | ||
Пусть G = (V, E) – геометрическая сеть, множество вершин V которой соответствует множеству из n точек в R d для определенного целого числа d > 2, а множество ребер E – множеству прямолинейных сегментов, соединяющих пары точек из V. Сеть G называется полной, если E соединяет все пары точек из V. | Пусть G = (V, E) – геометрическая сеть, множество вершин V которой соответствует множеству из n точек в R d для определенного целого числа d > 2, а множество ребер E – множеству прямолинейных сегментов, соединяющих пары точек из V. Сеть G называется полной, если E соединяет все пары точек из V. | ||
Стоимость 8(x, y) дуги, соединяющей пару точек x, y 2 Rd, равна евклидовому расстоянию между точками x и y. Иначе говоря, S(x, y) = P di=1(xi ~~ i)2, где x = (x1, ... , xd) и y = (y1, ... : : , yd). В более общем виде стоимость можно определить с использованием других норм – таких как lp-нормы для любого p > l, т.е. 8(x,y) = Pid=1(xi ~ yi)p. Стоимость сети представляет собой сумму стоимостей всех ребер сети: cost(G) = ^\x -,eE S(x, y). | |||
Версия от 13:03, 6 сентября 2016
Ключевые слова и синонимы
Геометрические графы; евклидовы графы
Постановка задачи
Рассматривается следующая классическая задача оптимизации: для заданной неориентированной взвешенной геометрической сети найти подсеть минимальной стоимости, удовлетворяющую заданным априори требованиям многосвязности.
Нотация
Пусть G = (V, E) – геометрическая сеть, множество вершин V которой соответствует множеству из n точек в R d для определенного целого числа d > 2, а множество ребер E – множеству прямолинейных сегментов, соединяющих пары точек из V. Сеть G называется полной, если E соединяет все пары точек из V.
Стоимость 8(x, y) дуги, соединяющей пару точек x, y 2 Rd, равна евклидовому расстоянию между точками x и y. Иначе говоря, S(x, y) = P di=1(xi ~~ i)2, где x = (x1, ... , xd) и y = (y1, ... : : , yd). В более общем виде стоимость можно определить с использованием других норм – таких как lp-нормы для любого p > l, т.е. 8(x,y) = Pid=1(xi ~ yi)p. Стоимость сети представляет собой сумму стоимостей всех ребер сети: cost(G) = ^\x -,eE S(x, y).