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

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

Текущая версия от 13:34, 1 сентября 2011

[math]\displaystyle{ \,(L,Y) }[/math]-Cвязка ([math]\displaystyle{ \,(L,Y) }[/math]-Bunch) — Пусть в связном графе [math]\displaystyle{ \,L = (X,U) }[/math] выделено некоторое подмножество вершин [math]\displaystyle{ Y \subset X; \,(L,Y) }[/math]-связкой называется тогда связный подграф графа [math]\displaystyle{ \,L }[/math], содержащий все вершины [math]\displaystyle{ \,Y }[/math] (но необязательно только их). Особый интерес представляют задачи нахождения такой связки с наименьшим числом вершин, минимальной по включению множества вершин и др.

Литература

  • Зыков А.А. Основы теории графов. — М.: Наука, 1984.