4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Материал из WEGA
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 22:01, 15 сентября 2016
, 15 сентября 2016→Нотация
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) м (→Нотация) |
||
| Строка 12: | Строка 12: | ||
Сеть G = (V, E) служит [[остов|остовом]] множества точек S (''охватывает'' множество точек S), если V = S. Сеть G является k-вершинно-связной, если для любого множества <math>U \subseteq \;</math>, состоящего из менее чем k вершин, сеть <math>(V \backslash U; E \cap ((V \backslash U) \times (V \backslash U))</math> является связной. Подобным же образом G является k-реберно-связной, если <math>\mathcal{E} \subseteq E \;</math> с количеством ребер менее k сеть <math>(V, E \backslash \mathcal{E}) \;</math> является связной. | Сеть G = (V, E) служит [[остов|остовом]] множества точек S (''охватывает'' множество точек S), если V = S. Сеть G является k-вершинно-связной, если для любого множества <math>U \subseteq \;</math>, состоящего из менее чем k вершин, сеть <math>(V \backslash U; E \cap ((V \backslash U) \times (V \backslash U))</math> является связной. Подобным же образом G является k-реберно-связной, если для любого множества <math>\mathcal{E} \subseteq E \;</math> с количеством ребер менее k сеть <math>(V, E \backslash \mathcal{E}) \;</math> является связной. | ||
