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

Материал из WEGA
Перейти к навигации Перейти к поиску

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