4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Перейти к навигации
Перейти к поиску
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 23:43, 6 сентября 2016
, 6 сентября 2016→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
== Нотация == | == Нотация == | ||
Пусть G = (V, E) – геометрическая сеть, множество вершин V которой соответствует множеству из n точек в | Пусть G = (V, E) – геометрическая сеть, множество вершин V которой соответствует множеству из n точек в Rd для определенного целого числа d > 2, а множество ребер E – множеству прямолинейных сегментов, соединяющих пары точек из V. Сеть G называется полной, если E соединяет все пары точек из V. | ||
| Строка 28: | Строка 28: | ||
Для заданного множества S из n точек в евклидовом пространстве Rd найти k-реберно-связную евклидову сеть минимальной стоимости, охватывающую точки S (в случае мультисети она может содержать параллельные ребра). | Для заданного множества S из n точек в евклидовом пространстве Rd найти k-реберно-связную евклидову сеть минимальной стоимости, охватывающую точки S (в случае мультисети она может содержать параллельные ребра). | ||
Понятие k-связности с минимальной стоимостью естественным образом расширяется на k-связность евклидова дерева Штейнера, если разрешить использование дополнительных вершин, называемых точками Штейнера. Для заданного набора точек S в пространстве Rd геометрическая сеть G представляет собой k-вершинно-связную (или k-реберно-связную) сеть Штейнера для S, если множество вершин G является надмножеством S и для каждой пары точек из S существует k внутренних вершинно-непересекающихся (реберно-непересекащихся, соответственно) путей, соединяющих их в G. | |||
(Евклидова) задача нахождения k-вершинно(реберно)-связной сети Штейнера минимальной стоимости | |||
Найти сеть минимальной стоимости на надмножестве S, являющуюся k-вершинно(реберно)-связной сетью Штейнера для S. | |||
Заметим, что при k = 1 эта задача представляет собой просто задачу построения минимального дерева Штейнера, которой посвящено множество работ (см., например, [14]). | |||
В более общей формулировке задач о многосвязности в графах следует учитывать ограничения неоднородной связности. | |||