![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Внешне устойчивым множеством Т вершин графа G называется такое множество его вершин, что для каждой вершины xi, не входящей в множество Т, существует дуга, исходящая из некоторой вершины множества Т и заходящая в вершину xi.
К задачам, которые решаются с помощью внешней устойчивости, относятся задачи о покрытиях: пусть имеется множество объектов. На этом множестве определить минимальное по мощности подмножество, которое держит под контролем все остальные элементы множества.
Задан граф. Определите все возможные внешне устойчивые подмножества вершин графа:
T1 = {X1, X4, X6}
T2 = {X1, X4}
T3 = {X3, X5, X6}
Внешне устойчивое множество вершин графа называется минимальным, если оно не содержит в качестве подмножеств другое внешне устойчивое множество.
Дата публикования: 2015-07-22; Прочитано: 5288 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!