Алгоритмы поиска максимальных независимых множеств графа и экспериментальная оценка их эффективности

• Автор: Фирюлина, Оксана Сергеевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Санкт-Петербург
• Количество страниц: 149 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

ГЛАВА 1. ЗАДАЧА О ПОИСКЕ МАКСИМАЛЬНЫХ НЕЗАВИСИМЫХ МНОЖЕСТВ

§1. Основные определения

§2. Постановка задачи о поиске максимальных независимых множеств

§3. Алгоритмы поиска максимальных независимых множеств в неориентированном графе

п. 1. Метод полного перебора и метод поиска с возвращением (алгоритм

Брона-Кербоша)

п. 2. Алгоритм Робсона и его модификация

ГЛАВА 2. АЛГОРИТМ ALLIS ПОСТРОЕНИЯ ВСЕХ МАКСИМАЛЬНЫХ НЕЗАВИСИМЫХ МНОЖЕСТВ НЕОРИЕНТИРОВАННОГО ГРАФА

§1. Основные определения

§2. Алгоритм AUIS построения всех максимальных независимых множеств
графа
§3. Теоретическое обоснование алгоритма AUIS
§4. Пример построения максимальных независимых множеств
§5. Тестирование программной реализации
ГЛАВА 3. АЛГОРИТМ MAXIS ПОИСКА НАИБОЛЬШЕГО НЕЗАВИСИМОГО МНОЖЕСТВА
§1. Модификация алгоритма AUIS для решения задачи о наибольшем независимом множестве
§2. Теоретическое обоснование алгоритма MaxIS
§3. Пример построения наибольшего независимого множества

§4. Тестирование программной реализации
ГЛАВА 4. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ АЛГОРИТМОВ MAXIS И ALLIS
§1. Поиск максимальной общей подструктуры органических соединений
§2. Построение потенциальных вторичных структур РНК.
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ 1. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДА ПОЛНОГО ПЕРЕБОРА ДЛЯ ПОИСКА НАИБОЛЬШЕГО НЕЗАВИСИМОГО МНОЖЕСТВА
ПРИЛОЖЕНИЕ 2. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДА ПОЛНОГО ПЕРЕБОРА ДЛЯ ПОСТРОЕНИЯ ВСЕХ МАКСИМАЛЬНЫХ НЕЗАВИСИМЫХ МНОЖЕСТВ
ПРИЛОЖЕНИЕ 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА БРОНА-КЕРБОША
ПРИЛОЖЕНИЕ 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА РОБСОНА
ПРИЛОЖЕНИЕ 5. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ALLIS
ПРИЛОЖЕНИЕ 6. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА MAXIS

ВВЕДЕНИЕ
Роль теории графов в математическом моделировании трудно переоценить. Модели на графах применяются в самых различных областях науки и техники: от социологии до компьютерных технологий. Это объясняется тем, что такие модели обладают высокой степенью наглядности и потому понятны и удобны в использовании.
Теория графов как один из важнейших разделов дискретной математики начала развиваться с 1930-х г [16]. Развитие вычислительной техники позволило обрабатывать графы больших размерностей. Но, несмотря на это, в теории графов до сих пор остаются задачи, которые имеют репутацию «трудно вычислимых», даже с использованием самых современных компьютерных технологий. Речь идет о так называемых NР-полных задачах. К таким задачам относят те, для которых в настоящее время не существует точных алгоритмов решения с полиномиальной оценкой сложности. Доказано существование несколько сотен IVР-полных задач [2], но, к сожалению, ни одна из них пока не может быть решена за полиномиальное время. Создание полиномиального точного алгоритма хотя бы одной из них привело бы к разработке эффективных алгоритмов для всех остальных задач данного класса. Это означало бы решение одной из основных проблем теории сложности, проблемы несовпадения слож-ностных классов Р ф NР [6]. Эту проблему можно сформулировать следующим образом: можно ли все задачи, решение которых проверяется с полиномиальной сложностью решить за полиномиальное время? В настоящее время нет теоретических доказательств как возможности, так и невозможности существования подобных алгоритмов решения. Проблема Р ф ИР неоднократно поднималась в работах разных авторов [7], [32], [37], [38]. Согласно проведенному исследованию публикаций последних лет (2001-2010гг.): [31], [34], [35], [36], [47], [55], [61], [70], [71], проблема поиска эффективных точных алгоритмов решения N Р-полных задач не прекращает привлекать к себе внимание

construct S^a*], A [a*] construct D[ak+l] for all ak+1 G S'fa*] end if
S[ak'x} := S[ak~l] {R{ah; U {a*}), к := к +
end if
end if
end do
return M(G)
end {of AllIS}
§3. Теоретическое обоснование алгоритма AllIS
Пусть неориентированный граф G представлен в виде: G = V,Sv,a- В дополнение к вершинам графа введем пару изолированных вершин оф1 = {Р*1,!*1), Для которых, очевидно, S[a-1] = SViA = {а?, а$,... а"},
т = IS'k.aI-
Для каждого элемента a0 G S’fa“1] построим базовое множество D[a°. Справедливы следующие теоремы.
Теорема 1. Любое максимальное независимое миоо/сество Qc[&] содержится в базовом множестве, соответствующем паре а = (/3,7):
Qc[а] С Da[oi).
Доказательство. Пусть существует вершина v* Da[a] : М = {/3,7, V*} -независимое множество вершин, индуцирующее безреберный подграф G' С G. По определению безреберного графа, его вершины /3, j и v* попарно несмежны, следовательно, вершина v* одновременно несмежна с /3 и 7 . Тогда по определению базового множества, должно выполняться условие v* G Аз[а]- Противоречие доказывает, что не существует безреберного подграфа, множество