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