Поиск максимального независимого множества графа с помощью алгоритмов Брона-Кэрбоша, Ткача, алгоритма поиска η-областей
Курсовая работа, 17 Ноября 2011, автор: пользователь скрыл имя
Описание
Этот граф устроен следующим образом. Вершины его - знакомые юбиляра. Две вершины смежны, если соответствующие знакомые друг другу не симпатизируют. Нетрудно понять, что число независимости этого графа и представляет тот самый максимальный контингент приглашенных, который может себе позволить юбиляр.
Таким образом, задача поиска наибольшего независимого множества заключается в нахождении наибольшего количества несмежных между собой вершин графа. Данная программа предлагает 3 алгоритма решения этой задачи.
Содержание
Введение 4
1.Математические методы 6
2.Постановка задачи 11
3.Разработка алгоритмов 12
3.1. Алгоритм Брона-Кэрбоша 12
3.2. Алгоритм Ткача 13
3.3. Алгоритм поиска η-областей 14
4.Описание программы 17
Выводы 19
Список использованных источников 20
Приложение А: Экранные формы 21
Приложение Б: код 22