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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Литература

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