Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Множество внешней устойчивости графа



Множество внешней устойчивости множество вершин, для которых выполняется одно из следующих правил:

1). Любая вершина входит в это множество

2) Либо вершина не входит в это множество, но из этой вершины есть дуга в данное множество.

Пусть дан граф . Тогда для множества внешней устойчивости справедливо следующее:

(3.12)

Число внешней устойчивости (β) – это наименьшая мощность из всех множеств внешней устойчивости.





Дата публикования: 2014-11-03; Прочитано: 405 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.01 с)...