4430
правок
Минимальные k-связные геометрические сети: различия между версиями
Материал из WEGA
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 13:23, 17 сентября 2016
, 17 сентября 2016→Нотация
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) м (→Нотация) |
||
| Строка 27: | Строка 27: | ||
'''(Евклидова) задача нахождения k-реберно-связной остовной мультисети минимальной стоимости''' | '''(Евклидова) задача нахождения k-реберно-связной остовной мультисети минимальной стоимости''' | ||
Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}^d \;</math> найти k-реберно-связную евклидову мультисеть минимальной стоимости, охватывающую точки S (под мультисетью понимается сеть, допускающая наличие параллельных ребер. | Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}^d \;</math> найти k-реберно-связную евклидову мультисеть минимальной стоимости, охватывающую точки S (под мультисетью понимается сеть, допускающая наличие ''параллельных'' ребер. | ||
Понятие k-связности с минимальной стоимостью естественным образом расширяется на k-связность евклидовой сети Штейнера, если разрешить использование дополнительных вершин, называемых точками Штейнера. Для заданного набора точек S в пространстве <math>\mathbb{R}^d \;</math> геометрическая сеть G представляет собой k-вершинно-связную (или k-реберно-связную) сеть Штейнера для S, если множество вершин G является надмножеством S и для каждой пары точек из S существует k внутренне вершинно-непересекающихся (реберно-непересекащихся, соответственно) путей, соединяющих их в G. | Понятие k-связности с минимальной стоимостью естественным образом расширяется на k-связность евклидовой сети Штейнера, если разрешить использование дополнительных вершин, называемых [[точки Штейнера|точками Штейнера]]. Для заданного набора точек S в пространстве <math>\mathbb{R}^d \;</math> геометрическая сеть G представляет собой k-вершинно-связную (или k-реберно-связную) сеть Штейнера для S, если множество вершин G является надмножеством S и для каждой пары точек из S существует k внутренне вершинно-непересекающихся (реберно-непересекащихся, соответственно) путей, соединяющих их в G. | ||
| Строка 46: | Строка 46: | ||
'''Задача построения сети с повышенной живучестью''' | '''Задача построения сети с повышенной живучестью''' | ||
Для заданного набора S точек в R и функции требования связности r: | Для заданного набора S точек в <math>\mathbb{R}^d \;</math> и функции требования связности <math>r: S \times S \to \mathbb{N} \;</math> найти геометрическую сеть минимальной стоимости, охватывающую точки из S, такую, что для любой пары вершин <math>p, q \in S \;</math> подсеть имеет грл внутренне вершинно-непересекающихся (или реберно-непересекащихся, соответственно) путей между p и q. | ||
