4194
правки
(L,Y)-Связка: различия между версиями
Материал из WEGA
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>(L,Y)</math>-Cвязка''' (''[[(L,Y)-Bunch|<math>(L,Y)</math>-Bunch]]'') | '''<math>\,(L,Y)</math>-Cвязка''' (''[[(L,Y)-Bunch|<math>\,(L,Y)</math>-Bunch]]'') — | ||
Пусть в [[связный граф|связном графе]] <math>L = (X,U)</math> выделено некоторое подмножество | Пусть в [[связный граф|связном графе]] <math>\,L = (X,U)</math> выделено некоторое подмножество | ||
[[вершина|вершин]] <math>Y \subset X | [[вершина|вершин]] <math>Y \subset X; \,(L,Y)</math>-связкой называется тогда связный [[подграф]] | ||
[[граф|графа]] <math>L</math>, содержащий все вершины <math>Y</math> (но необязательно только их). | [[граф|графа]] <math>\,L</math>, содержащий все вершины <math>\,Y</math> (но необязательно только их). | ||
Особый интерес представляют задачи нахождения такой связки с | Особый интерес представляют задачи нахождения такой связки с | ||
наименьшим числом вершин, минимальной по включению множества вершин и | наименьшим числом вершин, минимальной по включению множества вершин и | ||
др. | др. | ||
==Литература== | ==Литература== | ||
* Зыков А.А. Основы теории графов. — М.: Наука, 1984. | |||
