(L,Y)-Связка: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''<math>L,Y)</math>-Cвязка''' (''<math>L,Y)</math>-Bunch'') - Пусть в связном графе <math>L = (X,U)</math> выд...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>L,Y)</math>-Cвязка''' (''<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>; <math>(L,Y)</math>-связкой называется тогда связный подграф | [[вершина|вершин]] <math>Y \subset X</math>; <math>(L,Y)</math>-связкой называется тогда связный [[подграф]] | ||
графа <math>L</math>, содержащий все вершины <math>Y</math> (но необязательно только их). | [[граф|графа]] <math>L</math>, содержащий все вершины <math>Y</math> (но необязательно только их). | ||
Особый интерес представляют задачи нахождения такой связки с | Особый интерес представляют задачи нахождения такой связки с | ||
наименьшим числом вершин, минимальной по включению множества вершин и | наименьшим числом вершин, минимальной по включению множества вершин и | ||
Версия от 17:13, 29 января 2010
[math]\displaystyle{ (L,Y) }[/math]-Cвязка ([math]\displaystyle{ (L,Y) }[/math]-Bunch) - Пусть в связном графе [math]\displaystyle{ L = (X,U) }[/math] выделено некоторое подмножество вершин [math]\displaystyle{ Y \subset X }[/math]; [math]\displaystyle{ (L,Y) }[/math]-связкой называется тогда связный подграф графа [math]\displaystyle{ L }[/math], содержащий все вершины [math]\displaystyle{ Y }[/math] (но необязательно только их). Особый интерес представляют задачи нахождения такой связки с наименьшим числом вершин, минимальной по включению множества вершин и др.
Литература
[Зыков/84]