Диссертация (1149246), страница 7
Текст из файла (страница 7)
. , k. Учитывая тот факт, чтоv ∈ D[α∗k ], имеем, что ω[α∗k ] = D[α∗k ] \ {β∗k , γ∗k } = {v, δ, . . .}. По нашему предпоeложению множество J:Je = {β∗0 , γ∗0 , β∗1 , γ∗1 , . . . , β∗k , γ∗k , δ, v}является независимым множеством, то вершины v и δ несмежны, и следовательно, S[α∗k ] = {(v, δ)} ̸= ∅. Полученное противоречие доказывает тот факт, что комножеству J нельзя добавить ни одну вершину с сохранением независимости,и следовательно, J является максимальным независимым множеством.464) Этот случай можно назвать объединением случаев 1) и 3). Так какS[α∗k ] ̸= ∅ и ∆[α∗k ] ̸= ∅, то сначала по алгоритму сформируются МНМ, вкоторых последними добавленными вершинами будут элементы из множества∆[α∗k ], а затем, будут построены ветви дерева поиска, порожденные узлами измножества S[α∗k ].В результате прохождения прямого хода алгоритма, сформируется одна (случай 2) или несколько (случаи 3, 4) ветвей дерева поиска, соответствующихМНМ.
После их построения осуществляется возврат на предыдущий уровеньдерева поиска (k = k − 1) и формируются новые максимальные независимыемножества, с общей частью J = J \ {β k , γ k } (случай 2) или J = J \ {β k , γ k , δ}(случай 3).Рассмотрим простой пример. Пусть в графе G есть только одно максимальное независимое множество J = {1, 2, 4, 6, 7}. Построим дерево поиска,в соответствии с приведенными выше инструкциями (Рисунок 11).Рис.
11: Дерево поиска для МНМ J = {1, 2, 4, 6, 7} без использования в алгоритме AllISдополнительных процедур отсечения ветвей.Очевидно, что на нулевом уровне дерева поиска будут находитьсяl = m ∗ (m − 1)/2 узлов, где m – мощность максимального независимого47множества(в нашем примере m = 5, l = 10), рассмотрение которых приведет кпостроению одного и того же независимого множества J.
Кроме этого, когда мыспустимся на один уровень ниже, для каждого узла нулевого уровня появятсяеще (m − 2) ∗ (m − 3)/2 ответвлений, ведущих к формированию множестваJ = {1, 2, 4, 6, 7}. Учитывая, что |J| = 5, общее количество ветвей в деревепоиска будет равняться(m ∗ (m − 1)/2) ∗ ((m − 2) ∗ (m − 3)/2) ∗ (m − 4) = 10 ∗ 3 = 30.Таким образом, алгоритм должен обработать 30 ветвей дерева поиска, каждаяиз которых соответствует одному и тому МНМ.
Естественно, возникает вопрос:как предотвратить формирование уже построенных МНМ? Для этого в алгоритме AllIS предусмотрены процедуры исключения тех узлов, использованиекоторых не позволит построить множество, отличное от МНМ, уже сформированных в ходе алгоритма.Укажем критерии, по которым узлы будут рассматриваться как «неперспективные» для продолжения построения МНМ.Теорема 3. Пусть задан граф G = [V, SV,A ]. Если DG [α] ⊆ DG [α∗ ], тогдадля любого МНМ QG [α] ⊆ DG [α] найдется МНМ QG [α∗ ] ⊆ DG [α∗ ] такое чтоQG [α∗ ] ≡ QG [α] (другими словами, любое МНМ, содержащее вершины β и γ,будет являться МНМ, содержащим вершины β∗ и γ∗ ).Доказательство.
Рассмотрим произвольное максимальное независимоемножество QG [(β, γ)]DG [(β, γ)]⊆⊆DG [(β, γ)]. Поскольку по условию теоремыDG [(β∗ , γ∗ )], то QG [(β, γ)] также является подмножествомDG [(β∗ , γ∗ )]. Остается показать, что множество QG [(β, γ)] содержит элементыβ∗ и γ∗ . Предположим, что это не так. С учетом того, что множествоQG [(β, γ)] ⊆ DG [(β∗ , γ∗ )], вершины β∗ и γ∗ в графе G не смежны ни с однойвершиной из множества QG [(β, γ)]. Но тогда мы можем дополнить множествоQG [(β, γ)] элементами β∗ и γ∗ и получить независимое множество большегоразмера, включающее данное, что противоречит максимальности независимого48множества QG [(β, γ)]. Полученное противоречие доказывает, что любое максимальное независимое множество, содержащее вершины β и γ, будет являтьсямножеством, содержащим вершины β∗ и γ∗ :∀QG [α] ⊆ DG [α] ∃ QG [α∗ ] ⊆ DG [α∗ ] | QG [α∗ ] ≡ QG [α].Теорема 4.
Если в некотором подграфе Gk ⊂ Gk−1 ⊂ . . . ⊂ G0 для выбранного узла α∗k = (β∗k , γ∗k ) найдется множество Q ∈ P [α∗k ] :Q \ {β∗0 , γ∗0 , β∗1 , γ∗1 , . . . , β∗k−1 , γ∗k−1 } ≡ D[α∗k ],тогда максимальное независимое множествоJe = {β∗0 , γ∗0 , β∗1 , γ∗1 , . . . , β∗k−1 , γ∗k−1 } ∪ QGk [α∗k ] ≡ Q.Доказательство. Множество Q ∈ P [α∗k ], следовательно, по определениюокрестности:{β∗k , γ∗k , β∗k−1 , γ∗k−1 , .
. . , β∗0 , γ∗0 , } ⊆ Q.Обозначим, I = Q \ {β∗k−1 , γ∗k−1 , . . . , β∗0 , γ∗0 } = {β∗k , γ∗k , . . .}. По определениюбазового множества D[α∗k ] = {β∗k , γ∗k , . . .}. По условию теоремы I ≡ D[α∗k ],поэтому все элементы множества D[α∗k ] попарно несмежны (так как в этомслучае все вершины из базового множества содержатся во множестве Q, которое принадлежит окрестности P [α∗k ], а значит, является максимальным независимым множеством), следовательно, QGk [α∗k ] ≡ D[α∗k ]. Таким образом, длярасширения независимого множества J = {β∗0 , γ∗0 , β∗1 , γ∗1 , . .
. , β∗k−1 , γ∗k−1 } будутиспользованы все элементы множества D[α∗k ]. Полученное расширенное максимальное независимое множество Je можно представить в виде:Je = J ∪ D[α∗k ] = J ∪ I == {β∗0 , γ∗0 , β∗1 , γ∗1 , . . . , β∗k−1 , γ∗k−1 } ∪ (Q \ {β∗0 , γ∗0 , β∗1 , γ∗1 , . . . , β∗k−1 , γ∗k−1 }) ≡ Q,что и требовалось доказать.49В процессе работы алгоритма на каждом k-м уровне дерева поиска происходит выбор пары вершин α∗k = (β∗k , γ∗k ), используемых в дальнейшем длярасширения независимого множества J. Выбранный узел α∗k должен удовлетворять двум условиям:1) |D[α∗k ]| = maxαk ∈S[α∗k ] |D[αk ]| (для того чтобы как можно больше парвершин можно было исключить из дерева поиска после построения всех Q[α∗k ]);2) не должно существовать множества Q из окрестности P [α∗k ], удовлетворяющего условию теоремы 4 ( в противном случае, рассмотрение этого узлаприведет к формированию МНМ, которое уже было построено ранее).После добавления пары вершин α∗k = (β∗k , γ∗k ) ко множеству J, необходимоисключить этот узел из множества несмежных пар предыдущего уровня S[α∗k−1 ].Кроме этого из множества S[α∗k−1 ] удаляются узлы, удовлетворяющие условиютеоремы 3, так как они не позволят сформировать МНМ, отличное от того,которое мы построим, пройдя по одной из веток дерева поиска, порожденнойузлом α∗k = (β∗k , γ∗k ).§4.
Пример построения максимальных независимыхмножествДля графа, заданного матрицей смежности A (Рисунок 12), множество вершинV = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, множество несмежных парSV,A = {(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 10), (2, 3), (2, 5),(2, 6), (2, 7), (2, 8), (2, 9), (2, 10), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10),(4, 5), (4, 6), (4, 8), (4, 9), (5, 6), (5, 9), (5, 10), (6, 7), (6, 9), (6, 10), (7, 8),(7, 9), (8, 9), (8, 10), (9, 10)}.50Рис. 12: Матрица смежности графа G.В начале работы алгоритма AllIS имеем следующие входные данные:- уровень дерева поиска k = 0,- текущее независимое множество J = ∅,- максимальное независимое множество Q = ∅,- множество всех МНМ графа G M (G) = ∅,- вспомогательный узел отрицательного уровня α∗−1 = (α∗−1 , β∗−1 ),- окрестность P [α∗−1 ] = ∅,- опорное множество ω[α∗−1 ] ≡ V ,- S[α∗−1 ] ≡ SV,A .На Рисунках 13 и 14 компактно представлена часть процедуры построениямаксимальных независимых множеств по алгоритму AllIS.
Поясним некоторыемоменты его работы.Сначала формируем базовые множества D[α0 ] для всех несмежных парα0 ∈ S[α∗−1 ] ≡ SV,A графа G. Затем в качестве ведущего элемента на нулевомуровне выбираем узел α∗0 = (2, 3), так как он удовлетворяет условию:|D[(2, 3)]| = maxα0 ∈S[α∗−1 ] |D[α0 ]| = 9.51Рис. 13: Пример реализации алгоритма AllIS.52Рис. 14: Пример реализации алгоритма AllIS.53Окрестность P [(2, 3)] = ∅. Выбрав ведущий элемент, формируем множество«неперспективных» узлов R[(2, 3)], которые в дальнейшем будут удалены измножества S[α∗−1 ], с целью не допустить построения повторяющихся МНМ.Далее для выбранного узла α∗0 = (2, 3) строим опорное множествоω[(2, 3)] = D[(2, 3)] \ {2, 3} = {1, 5, 6, 7, 8, 9, 10}.Вершины 2 и 3 становятся элементами независимого множества J = {2, 3}. Вподрафе, индуцированном множеством ω[(2, 3)], строим множество несмежныхпар S[(2, 3)].
Для каждого узла из S[(2, 3)] формируем базовые множества.По мощности базового множества выбираем ведущий элемент первого уровняα∗1 = (1, 6). Расширяем независимое множетво J = {2, 3, 1, 6}. Среди вершинопорного множестваω[(1, 6)] = D[(1, 6)] \ {1, 6} = {5, 7, 10}только 5 и 10 являются несмежными, поэтомуS[(1, 6)] = {(5, 10)}, ∆[(1, 6)] = {7}.Так как множество ∆[(1, 6)]̸=∅, то можно сразу выписать МНМQ = J ∪ {7} = {1, 2, 3, 6, 7}.
После нахождения очередного МНМ необходимопополнить окрестности всех ведущих узлов текущей ветви дерева поиска:P [(β∗−1 , γ∗−1 )] = P [(2, 3)] = P [(1, 6)] = {{1, 2, 3, 6, 7}}.После выбора в качестве очередного ведущего узла α∗2 = (5, 10) (текущее множество J = {2, 3, 1, 6, 5, 10}) приходим к ситуацииω[(5, 10)] = D[(5, 10)] \ {5, 10} = ∅.Таким образом формирование текущей ветви дерева поиска закончено. Независимое множество J является максимальным независимым. Пополняем соответствующие окрестности:P [(β∗−1 , γ∗−1 )] = P [(2, 3)] = P [(1, 6)] = {{1, 2, 3, 6, 7}, {1, 2, 3, 5, 6, 10}}.54Исключаем из множества J последний ведущий элемент:J = {1, 2, 3, 5, 6, 10} \ {5, 10} = {1, 2, 3, 6},и возвращаемся на предыдущий уровень (k = k − 1, k = 1).
Так как послепостроения МНМ, содержащих узел α∗2 = (5, 10), множествоS[α∗k ] = {(5, 10)} \ {(5, 10)},то следует вернуться еще на один уровень назад:k = k − 1, k = 0, J = {1, 2, 3, 6} \ {1, 6} = {2, 3}.Ведущий элемент α∗1 = (1, 10), опорное множество ω[(1, 10)] = {5, 6, 8},S[(1, 10)] = {(5, 6)}, ∆[(1, 10)] = {8}. Так как множество ∆[(1, 10)] ̸= ∅, томожно сразу выписать МНМ Q = J ∪ {8} = {1, 2, 3, 8, 10}.Аналогичным способом строятся все ветви дерева поиска, идущие из узлаα∗0 = (2, 3) (Рисунок 15).Рис.
15: Дерево поиска по алгоритму AllIS.После обработки α∗0 происходит пополнение множества R[α∗0 ] узлов, рассмотрение которых приведет к построению уже сформированных МНМ:55R[(2, 3)] = {(1, 2), (1, 3), (1, 7), (1, 10), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (2, 10),(3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10), (5, 10), (6, 7), (6, 10), (7, 8), (7, 9),(8, 10), (9, 10)}.После исключения элементов, принадлежащих множеству R[(2, 3))], из множества S[α∗−1 ], переходим к обработке оставшихся узлов нулевого уровня. Витоге получаем дерево поиска (Рисунок 15), каждая ветвь которого отвечаетуникальному максимальному независимому множеству исходного графа.§5. Тестирование программной реализацииВ ходе исследования алгоритма AllIS было обнаружено, что при одной итой же размерности время работы алгоритма может существенно различаться.Это объясняется разной плотностью ребер (в дальнейшем плотностью) генерируемых графов.
Таким образом функция f (n, p) времени работы алгоритмаявляется функцией двух параметров: размерности (n) и плотности (p).Принимая во внимание установленную зависимость работы алгоритма AllISот плотности графов, были проведены тесты двух типов:1) определение времени работы алгоритмов при увеличении плотности обрабатываемых графов в пределах фиксированной размерности;2) определение времени работы алгоритмов при увеличении размерностиграфов фиксированной плотности.Для тестирования генерировались графы с различными значениями плотности. С этой целью в программе по заданной плотности p (%) определялоськоличество ребер r n-вершинного графа G = (V, E): r =p·m100% ,где m =n·(n−1).2Полученное значение r округлялось до целого числа.
Далее, используя функциюгенерации случайных чисел, формировались пары вершин (i, j): i – случайноечисло из промежутка [1, n − 1], j – из промежутка [i + 1, n]. Каждая такая паразаписывалась во множество ребер E в том случае, если она не была добавлена56ранее. Множество E продолжало расширяться, пока его мощность не достигалазначения r.В процессе тестирования графов одной и той же размерности были рассмотрены графы со значением плотности p ∈ [0%, 100%] с шагом равным 1%. Количество графов для каждого значения плотности равнялось 10. В качестве результирующего времени работы выбиралось среднее арифметическое значениевремени для графов с одинаковыми характеристиками [n, p].Наряду с AllIS в тестировании участвовали еще два алгоритма, предназначенных для поиска всех максимальных независимых множеств в неориентированном графе: алгоритм Брона-Кербоша и полный перебор.Все алгоритмы были реализованы в пакете Maple 14. Тесты проводились накомпьютере с техническими характеристиками: процессор Intel Core i5 2.6 GHz4 GB RAM, ОС Windows 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
