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

и 2013 г.), всероссийской конференции, посвященной 80-летию со дня рождения В. И. Зубова «Устойчивость ипроцессы управления» (Санкт-Петербург, 2010 г.), XIII всероссийском симпозиуме по прикладной и промышленной математике (Петрозаводск, 2012 г.).Публикации. По теме диссертации опубликовано 8 работ, в том числедве статьи в журнале, входящем в перечень изданий, рекомендованных ВАК.Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, приложения и списка литературы, включающего 72 наименования. Общий объем работы составляет 101 страницу, невключая объем приложения, равный 48 страницам.СОДЕРЖАНИЕ РАБОТЫВо введении обосновывается актуальность темы исследования, степеньее разработанности, научная новизна, теоретическая и практическая значимость результатов, выносимых на защиту, а также приведено краткое содержание диссертационной работы.7В первой главе приведена постановка задачи поиска максимальных независимых множеств неориентированного графа, а также обзор существующих методов ее решения.

Кроме этого в заключительном параграфе главыпредставлена модификация известного алгоритма Робсона, которая была предложена автором, для формирования элементов наибольшего независимогомножества, а не только мощности этого множества, как это было сделано воригинальной работе Робсона.Вторая глава диссертации посвящена разработке нового алгоритма поиска всех МНМ графа – алгоритма AllIS. В первом параграфе даны основныеопределения и базовые конструкции разработанного алгоритма. Объектомисследования является неориентированный n-вершинный граф G = (V, E),заданный матрицей смежности A = ∥ai,j ∥n,n : 1, (i, j) ∈ E,ai,j = 0, (i, j) ∈/ E.Для использования алгоритма AllIS граф G представляется в видеG=[V, SV,A ], где V={1, 2, . . .

, n} — множество вершин графа,SV,A = {(p, q) | (p, q) ∈ V [2] & ap,q = 0} — множество всех несмежных парразличных вершин графа G. Любая пара несмежных вершин (β, γ) ∈ SV,Aназывается узлом и обозначается α = (β, γ). Базовым множеством для некоторого узла α = (β, γ) ∈ SV,A графа G назовем множествоDG [α] = {d ∈ V | (d, β) ∈ SV,A & (d, γ) ∈ SV,A } ∪ {β, γ}.Опорным множеством для этого же узла называется множествоωG [α] = DG [α]\{β, γ}.Независимое множество вершин в графе G обозначается QG , независимоемножество, в котором содержатся две вершины β и γ – QG [α], множествовсех вершин, имеющих ребро с каждой вершиной рассматриваемого графа –∆G [α], множество всех МНМ графа – M (G).8Процесс построения МНМ графа можно представить в виде дерева поиска,в котором каждый k-й уровень отвечает рассмотрению некоторого подграфаGk ⊂ Gk−1 ⊂ .

. . ⊂ G0 ≡ G.Подграф Gk+1 ⊂ Gk будем задавать в следующем виде:Gk+1 = [ω[α∗k ], S[α∗k ]], α∗k+1 ∈ S[α∗k ].Для компактной формализации алгоритма введем узел отрицательного уровня с вершинами, не имеющими ребра ни с одной вершиной графа G, и обозначим его α∗−1 = (β∗−1 , γ∗−1 ): ω[α∗−1 ] ≡ V, S[α∗−1 ] ≡ SV,A .Базовое множество D[αk+1 ] для узла αk+1 = (β k+1 , γ k+1 ) ∈ S[α∗k ] графаGk+1 представим какD[αk+1 ] = {d ∈ ω[α∗k ] | (d, β k+1 ) ∈ S[α∗k ] & (d, γ k+1 ) ∈ S[α∗k ]} ∪ {β k+1 , γ k+1 }.Опорное множество ω[α∗k+1 ] для узла α∗k+1 = (β∗k+1 , γ∗k+1 ) ∈ S[α∗k ] графа Gk+1определяем по правилуω[α∗k+1 ] = D[α∗k+1 ] \ {β∗k+1 , γ∗k+1 }.Множество S[α∗k+1 ] несмежных пар в графе, индуцированном множествомвершин ω[α∗k+1 ] :[2]S[α∗k+1 ] = {(p, q) | (p, q) ∈ ω[α∗k+1 ] & ap,q = 0}.Находим множество ∆[α∗k+1 ] по правилу∆[α∗k+1 ] = ω[α∗k+1 ] \ ∪(p,q)∈S[α∗k+1 ] {p, q}.Множество P [α∗k+1 ], сформированное согласно правилуP [α∗k+1 ] = {Q[α∗k ] ∈ P [α∗k ] | {β∗k+1 , γ∗k+1 } ⊆ Q[α∗k ]}, P [α∗−1 ] = ∅,будем называть окрестностью узла α∗k+1 .9Обсуждение основных моментов работы алгоритма, а также его псевдокод, приведены во втором параграфе.

В третьем параграфе доказываютсятеоремы, обеспечивающие теоретическое обоснование корректности работыалгоритма.Теорема 1. Любое максимальное независимое множество QG [α] содержится в базовом множестве, соответствующем паре α = (β, γ):QG [α] ⊆ DG [α].Теорема 2. Пусть QiG [α] – i-е МНМ графа G, содержащее вершины β иγ, m – количество всех таких множеств. ТогдаiDG [α] \ ∪mi=1 QG [α] = ∅.Согласно теореме 1 и теореме 2, для того чтобы построить максимальныенезависимые множества, содержащие в себе некоторую пару элементовα = (β, γ), необходимо использовать элементы базового множества для указанной пары.На основе следующей группы теорем (теорема 3 и теорема 4) формулируются критерии, по которым узлы рассматриваются как «неперспективные»для продолжения построения максимальных независимых множеств.Теорема3.

Если DG [α]DG [α∗ ], тогда для любого МНМ⊆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.10В процессе работы алгоритма на каждом k-м уровне дерева поиска происходит выбор пары вершин α∗k = (β∗k , γ∗k ), используемых в дальнейшем длярасширения независимого множества J. Выбранный узел α∗k должен удовлетворять двум условиям:1) |D[α∗k ]| = maxαk ∈S[α∗k ] |D[αk ]| (для того чтобы как можно больше парвершин можно было исключить из дерева поиска после построения всех Q[α∗k ]);2) не должно существовать множества Q из окрестности P [α∗k ], удовлетворяющего условию теоремы 4 (в противном случае, рассмотрение этого узлаприводит к формированию максимального независимого множества, котороеуже было построено ранее).Подробный пример использования алгоритма AllIS для решения задачио поиске всех МНМ приведен в четвертом параграфе.

Заключительный параграф главы посвящен тестированию программной реализации разработанногоалгоритма. Представлены результаты сравнения алгоритма AllIS c известнымалгоритмом Брона-Кербоша, а также методом полного перебора. Согласнорезультатам исследования время работы алгоритмов AllIS и Брона-Кербошасущественно зависит от плотности ребер графа. На тестируемом наборе матриц при низком значении плотности ребер алгоритм AllIS показал лучшиерезультаты, чем алгоритм Брона-Кербоша (Рисунки 1, 2).В третьей главе предложен новый алгоритм решения задачи о поискенаибольшего независимого множества в произвольном неориентированномграфе – алгоритм MaxIS, псевдокод которого приведен в первом параграфе.Алгоритм M axIS является модификацией алгоритма AllIS, рассмотренного впредыдущей главе.

Обсуждение изменений, проведенных в алгоритмеAllIS, а также доказательства теорем, обеспечивающих правомерность этихизменений, приведены во втором параграфе. Основное изменение в алгоритмеMaxIS – это введение отсечения ветвей дерева поиска, исходя из мощностибазового множества выбранного узла.11Рис. 1: Зависимость времени работы алгоритмов Брона-Кербоша и AllIS от плотностиребер графов при фиксированной размерности.б)а)Рис.

2: Зависимость времени работы алгоритмов Брона-Кербоша и AllIS от размерностиграфов при значении плотности ребер p = 6% (a) и p = 4% (б).Справедлива следующая теорема:Теорема 5. Если в некотором подграфе Gk ⊂ Gk−1 ⊂ . . . ⊂ G0 длябазового множества выбранного узла α∗k = (β∗k , γ∗k ) выполнено условие:|D[α∗k ]| + 2k ≤ |Qmax |,тогда мощность независимого множества, содержащего пару вершин β∗k , γ∗k ,не превзойдет мощности текущего наибольшего независимого множества:|Q[α∗k ]| ≤ |Qmax |.12Второе изменение в алгоритме MaxIS – это отказ от использования окрестностей.

Доказывается, что в отличие от алгоритма AllIS, для нахождениянаибольшего независимого множества использовать окрестность нецелесообразно. И наконец, третье изменение связано с подсчетом количества элементов множества S[α∗k ] после принятия решения о построении ветви деревапоиска, идущей из текущего выбранного узла α∗k . Пусть |ω[α∗k ]| = m.1) Если |S[α∗k ]| =m(m−1),2значит, опорное множество ω[α∗k ] целиком пред-ставляет собой независимое множество.

В этом случае, текущим наибольшимнезависимым множеством будет множествоQmax = {β∗0 , γ∗0 , β∗1 , γ∗1 , ..., β∗k−1 , γ∗k−1 } ∪ ω[α∗k ].2) Условие |S[α∗k ]| =m(m−1)2− 1 говорит о том, что среди элементов опорногомножества ω[α∗k ] только две вершины соединены ребром. В случае выполненияусловия |D[α∗k ]|+2k−1 > |Qmax |, в качестве нового наибольшего независимогомножества будет выступать множествоQmax = {β∗0 , γ∗0 , β∗1 , γ∗1 , ..., β∗k−1 , γ∗k−1 } ∪ (ω[α∗k ] \ {δ}),где вершина δ – одна из пары вершин опорного множества ω[α∗k ], которыесоединены между собой ребром.3) В случае, когда |S[α∗k ]| =m(m−1)2− 2, некоторые вершины опорногомножества ω[α∗k ] соединены ребрами, причем количество ребер однозначноравно двум, а количество вершин, инцидентных этим ребрам, может бытьравно либо трем, либо четырем. В такой ситуации нужно определить сколькоразличных вершин участвует в образовании ребер.Если количество различных вершин равно трем, значит, необходимо проверить условие:|D[α∗k ]| + 2k − 1 > |Qmax |.13В случае его выполненияQmax = {β∗0 , γ∗0 , β∗1 , γ∗1 , ..., β∗k−1 , γ∗k−1 } ∪ (ω[α∗k ] \ {δ}),где вершина δ инцидентна обоим ребрам.Если же количество различных вершин равно четырем, то при выполнении условия |D[α∗k ]| + 2k − 2 > |Qmax | наибольшим независимым множествомбудетQmax = {β∗0 , γ∗0 , β∗1 , γ∗1 , ..., β∗k−1 , γ∗k−1 } ∪ (ω[α∗k ] \ {δ1 , δ2 }),где вершины δ1 и δ2 инцидентны разным ребрам.В третьем параграфе поиск наибольшего независимого множества по алгоритму M axIS проиллюстрирован на примере обработки неориентированного 10-вершинного графа.