(L,Y)-Связка

Материал из WEGA
Версия от 16:15, 26 января 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''<math>L,Y)</math>-Cвязка''' (''<math>L,Y)</math>-Bunch'') - Пусть в связном графе <math>L = (X,U)</math> выд...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

[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]