Введение
ГЛАВА 1. Задача о поиске максимальных независимых множеств
1. Основные определения 11
2. Постановка задачи о поиске максимальных независимых множеств 14
3. Алгоритмы поиска максимальных независимых множеств в неориентиро ванном графе 16
п. 1. Метод полного перебора и метод поиска с возвращением (алгоритм Брона-Кербоша) 20
п. 2. Алгоритм Робсона и его модификация 23
ГЛАВА 2. Алгоритм allis построения всех макси-мальныхнезависимыхмножествнеориентирован-ного графа
1. Основные определения 30
2. Алгоритм AllIS построения всех максимальных независимых множеств графа 32
3. Теоретическое обоснование алгоритма AllIS 35
4. Пример построения максимальных независимых множеств 49
5. Тестирование программной реализации 55
ГЛАВА 3. Алгоритм maxis поиска наибольшего независимого множества
1. Модификация алгоритма AllIS для решения задачи о наибольшем независимом множестве 62
2. Теоретическое обоснование алгоритма MaxIS 64
3. Пример построения наибольшего независимого множества 69
4. Тестирование программной реализации 77
ГЛАВА 4. Практическое применение алгоритмов maxis и allis
1. Поиск максимальной общей подструктуры органических соединений...83
2. Построение потенциальных вторичных структур РНК 88
Заключение 92
Список литературы 94
