Аноним

(L,Y)-Связка: различия между версиями

Материал из WikiGrapp
нет описания правки
(Создана новая страница размером '''<math>L,Y)</math>-Cвязка''' (''<math>L,Y)</math>-Bunch'') - Пусть в связном графе <math>L = (X,U)</math> выд...)
 
Нет описания правки
Строка 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> (но необязательно только их).
Особый интерес представляют задачи нахождения такой связки с
Особый интерес представляют задачи нахождения такой связки с
наименьшим числом вершин, минимальной по включению множества вершин и
наименьшим числом вершин, минимальной по включению множества вершин и