Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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


 

Множество внутренней устойчивости графа – это множество несмежных вершин.

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

(3.4)

Максимальным множеством внутренней устойчивости называется внутренне устойчивое множество, добавление любой вершины к которому, делает это множество неустойчивым.

ПРИМЕР

Дан граф

Рис. 3.6 Граф

 

Данный граф имеет следующие множества внутренней устойчивости.

Рассмотрим множество . Добавляя к нему любую вершину, получаем множества внутренне неустойчивые: . Следовательно, множество является максимальным множеством внутренней устойчивости.

 

Числом внутренней устойчивости (α) называется число, равное наибольшей мощности максимального внутренне устойчивого множества.

Очевидно, что поиск максимальных внутренне устойчивых множеств путем простого перебора является неэффективной процедурой, поэтому для поиска максимальных внутренне устойчивых множеств существует специальный алгоритм – алгоритм Магу.

 

<== предыдущая лекция | следующая лекция ==>
Ядро графа | Алгоритм Магу для определения множества внутренней устойчивости графа

Дата добавления: 2014-01-04; Просмотров: 604; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.001 сек.