Диссертация (1149246), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

The elements of S are s1 , s2 , ... with d(si ) ≤ d(si+1 )}28(13) if |S| ≤ 1 then return {∅};(14) if |S| = 2 then if edge(s1 , s2 ) then return {∅};(15) else return {s1 , s2 } ∪ ms(G − N (s1 ) − N (s2 ));if |S| = 3 thenbegin(16) if d(s1 ) = 0 then return {s1 } ∪ ms1 (G − s1 , S − s1 );(17) if edge(s1 , s2 ) and edge(s2 , s3 ) and edge(s3 , s1 ) then return {∅};(18) return {sj , sk } ∪ ms(G − N (sj ) − N (sk ))(19) if edge(si , sj ) then return {sk } ∪ ms1 (G − N (sk ), [si , sj ]);(20) if d(s1 ) = 1 then return {s1 } ∪ ms1 (G − N (s1 ), S − s1 );(21) max1 := 1 + |ms1 (G − N (s1 ), S − s1 )|;max2 := 2 + |ms2 (G − N (s2 ) − N (s3 ) − s1 , N (s1 ))|;if max(max1 , max2 ) = max1 thenreturn {s1 } ∪ ms1 (G − N (s1 ), S − s1 );else return {s2 , s3 } ∪ ms2 (G − N (s2 ) − N (s3 ) − s1 , N (s1 ));if |S| = 4 then(22) max1 := 1 + |ms(G − N (s1 ))|;max2 := |ms2 (G − s1 , S − s1 )|;if max(max1 , max2 ) = max1 then return {s1 } ∪ ms(G − N (s1 ));else return ms2 (G − s1 , S − s1 );end {of ms2 }Следует отметить, что в оригинальной версии алгоритма в [60] в строчке(21) было написано:max(1 + ms1 (G − N (s1 ), S − s1 ), ms2 (G − N (s2 ) − N (s3 ) − s1 , N (s1 ))).Доскональное изучение алгоритма Робсона позволило установить ошибочностьэтой записи (видимо, была допущена опечатка).

Во второй части max() к значению функции ms2 должно прибавляться число 2. Числа, которые прибавляются29к результатам вычислений функций ms, ms1 и ms2 , имеют большое значениедля алгоритма, так как они показывают, сколько именно элементов будет добавлено к текущему независимому множеству. И если руководствоваться тойзаписью, которая приведена в [60], то вершины s2 и s3 не будут входить вискомое множество, что является ошибкой, так как текущее независимое множество расширяется двумя вершинами s2 и s3 , а следующими кандидатами надобавление в это множество становятся вершины из множества N (s1 ).Основные процедуры алгоритма Робсона применяются к связным графам,поэтому в качестве вспомогательного метода для выделения компонент связности был использован алгоритм поиска в глубину [16]. С программной реализацией алгоритма Робсона можно ознакомиться в приложении 4.30ГЛАВА 2. АЛГОРИТМ ALLIS ПОСТРОЕНИЯ ВСЕХМАКСИМАЛЬНЫХ НЕЗАВИСИМЫХ МНОЖЕСТВНЕОРИЕНТИРОВАННОГО ГРАФА§1.

Основные определенияПусть n-вершинный неориентированный граф без петель G = (V, E) заданматрицей смежности A = ∥ai,j ∥n,n : 1, (i, j) ∈ E,ai,j = 0, (i, j) ∈/ E.Очевидно, что матрица A является симметричной с нулевыми диагональнымиэлементами (в силу неориетированности графа G и отсутствия у него петель).Граф 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 } ∪ {β, γ}.Опорным множеством для некоторого узла α = (β, γ) ∈ SV,A графа G будемназывать множествоωG [α] = DG [α] \ {β, γ}.Обозначим QG — максимальное независимое множество вершин в графе G,QG [α] — максимальное независимое множество, в котором содержатся две вершины β и γ, ∆(G) — множество всех вершин, имеющих ребро с каждой вершиной рассматриваемого графа.31Множество всех максимальных независимых множеств графа G будем обозначать M (G).Процесс построения МНМ графа можно представить в виде дерева поиска,в котором каждый k-й уровень отвечает рассмотрению некоторого подграфа:Gk ⊂ Gk−1 ⊂ .

. . ⊂ G0 ≡ G.Пусть αk = (β k , γ k ) – некоторый узел в соответствующем графе Gk , индуцированном множеством ωGk−1 [αk−1 ]. Узлы αk и αk−1 связаны следующим образом:αk ∈ SωGk−1 [αk−1 ],A . Для компактности записи можно опустить индекс Gk умножества ωGk [αk ], так как по индексу узла αk однозначно можно определить,из вершин какого графа формируется опорное множество ω[αk ].Учитывая тот факт, что любой подграф Gk , Gk−1 ,. . . , G0 является подграфом G, а множества несмежных пар в них определяются: Sω[ αk−1 ],A , Sω[ αk−2 ],A ,Sω[ α0 ],A соответственно, то индекс A у множества S также можно опустить,понимая, что все несмежные пары вершин в указанных подграфах несмежныи в исходном графе с матрицей смежности A.

Множество Sω[ αk ],A будем записывать в виде S[αk ].Подграф Gk+1 ⊂ Gk будем задавать в следующем виде:Gk+1 = [ω[α∗k ], S[α∗k ]], α∗k+1 ∈ S[α∗k ].Для компактной формализации алгоритма введем узел α∗−1 = (β∗−1 , γ∗−1 ) отрицательного уровня с вершинами, не имеющими ребра ни с одной вершинойграфа G:ω[α∗−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 }.32Опорное множество ω[α∗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 ], S[α∗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 .§2.

Алгоритм AllIS построения всех максимальныхнезависимых множеств графаАлгоритм построения максимальных независимых множеств (алгоритмAllIS ), речь о котором пойдет в данном параграфе, базируется на способе выделения структурных особенностей (0,1)-матриц [10], [11], [12] и по сути являетсяего модификацией. Каждая ветвь дерева поиска, порожденная алгоритмомAllIS, соответствует уникальному независимому множеству. Каждое построенное такое множество является максимальным независимым. Определенныемеханизмы отсечения ветвей дерева поиска позволяют не допустить повторного построения уже сформированных множеств, что существенно сокращаетпроцесс решения задачи.Рассмотримосновныемоментыработыалгоритма.Выбравузелα∗0 = (β∗0 , γ∗0 ) ∈ SV,A в графе G0 ≡ G, строим для него опорное множество33ωG0 [α∗0 ].

Задача нахождения МНМ, содержащего вершины β∗0 , γ∗0 , в графе Gсводится к поиску МНМ в подграфе G1 ⊂ G0 , индуцированном множествомвершин ωG0 [α∗0 ] ⊆ V , а затем объединению каждого найденного МНМ в G1 спарой вершин (β∗0 , γ∗0 ). Для нахождения максимального независимого множества в подграфе G1 = [ωG0 [α∗0 ], SωG0 [α∗0 ],A ] используется та же схема. Выбираемузел α∗1 = (β∗1 , γ∗1 ) ∈ SωG0 [α∗0 ],A , строим для него опорное множество ωG1 [α∗1 ] ипереходим к нахождению МНМ в подграфе G2 ⊂ G1 ⊂ G0 . Таким образом,выбрав некоторую пару вершин в графе, переходим к соответствующему подграфу, тем самым сужая размерность задачи.

Ниже представлен псевдокодалгоритма AllIS :procedure AllIS ( G = [V, SV,A ] )begink := 0 //номер текущего уровня дерева поискаJ := ∅ //независимое множествоQ := ∅ //максимальное независимое множествоM (G) := ∅ //множество всех МНМ графа Gα∗−1 := (β∗−1 , γ∗−1 ) //дополнительный узел отрицательного уровняR[α∗−1 ] := ∅ //множество узлов, использование которых не позволитпостроить новое уникальное МНМZ∆ := ∅ //множество вершин, которые удаляются из множества ∆[α∗k ]P [α∗k−1 ] := ∅ //окрестность дополнительного узлаω[α∗k−1 ] := V //множество вершин исходного графаS[α∗k−1 ] := SV,A //множество пар несмежных вершин исходного графаconstruct ∆[α∗k−1 ]αk := (β k , γ k ) ∈ SV,A , β k , γ k ∈ Vconstruct D[αk ]continue := truewhile continue = true do∆[α∗k−1 ] := ∆[α∗k−1 ] \ Z∆34while ∆[α∗k−1 ] ̸= ∅ do∀δ∗ ∈ ∆[α∗k−1 ] do Q := J ∪ {δ∗ }, M (G) := M (G) ∪ {Q}for ξ := −1 to k − 1 do P [α∗ξ ] := P [α∗ξ ] ∪ {Q} end do∆[α∗k−1 ] := ∆[α∗k−1 ] \ {δ∗ }end doif S[α∗k−1 ] = ∅ thenif k = 0 then continue := f alseelse J := J \ {β∗k−1 , γ∗k−1 },k := k − 1end ifelsechoose α∗k := (β∗k , γ∗k ) ∈ S[α∗k−1 ] : |D[α∗k ]| = maxαk ∈S[α∗k−1 ] |D[αk ]|R[α∗k ] := {(β k , γ k ) | D[αk ] ⊆ D[α∗k ], (β k , γ k ) ∈ S[α∗k−1 ] \ {α∗k }}Z∆ := ∅construct P [α∗k ]exist := 0for all L ∈ P [α∗k ] doif |(L \ J) \ {β∗k , γ∗k }| = 1 then Z∆ := Z∆ ∪ (L \ J) \ {β∗k , γ∗k }if |D[α∗k ]| = 3 then exist := 1 end ifelseif |D[α∗k ]| = |L \ J| then exist := 1 end ifend ifend doif exist = 1 then S[α∗k−1 ] := S[α∗k−1 ] \ (R ∪ {α∗k })else J := J ∪ {β∗k , γ∗k },construct ω[α∗k ]if ω[α∗k ] = ∅ then S[α∗k ] := ∅, ∆[α∗k ] := ∅,Q := J, M (G) := M (G) ∪ {Q}for ξ := −1 to k − 1 do P [α∗ξ ] := P [α∗ξ ] ∪ {Q} end do35elseconstruct S[α∗k ], ∆[α∗k ]construct D[αk+1 ] for all αk+1 ∈ S[α∗k ]end ifS[α∗k−1 ] := S[α∗k−1 ] \ (R[α∗k ] ∪ {α∗k }), k := k + 1end ifend ifend doreturn M (G)end {of AllIS }§3.

Теоретическое обоснование алгоритма AllISПусть неориентированный граф G представлен в виде: G = [V, SV,A ]. Вдополнениеквершинамграфавведемпаруизолированныхвершинα∗−1 = (β∗−1 , γ∗−1 ), для которых, очевидно, S[α∗−1 ] ≡ SV,A = {α10 , α20 , .

. . ατ0 },τ = |SV,A |.Для каждого элемента α0 ∈ S[α∗−1 ] построим базовое множество D[α0 ].Справедливы следующие теоремы.Теорема 1. Любое максимальное независимое множество QG [α] содержится в базовом множестве, соответствующем паре α = (β, γ):QG [α] ⊆ DG [α].Доказательство. Пусть существует вершина v∗ ∈/ DG [α] : M = {β, γ, v∗ } –независимое множество вершин, индуцирующее безреберный подграф G′ ⊂ G.По определению безреберного графа, его вершины β, γ и v∗ попарно несмежны,следовательно, вершина v∗ одновременно несмежна с β и γ .

Тогда по определению базового множества, должно выполняться условие v∗ ∈ DG [α]. Противоречие доказывает, что не существует безреберного подграфа, множество36вершин которого содержит пару (β, γ) и какой-либо элемент, не принадлежащий базовому множеству, соответствующему указанной паре. Таким образом,множества вершин, индуцирующие безреберный подграф, а, следовательно, ивсе максимальные независимые множества, имеющие в качестве двух своихвершины β и γ, целиком содержатся в базовом множестве DG [α].Теорема 2. Пусть QiG [α] – i-е максимальное независимое множествографа G, содержащее вершины β и γ, m – количество всех таких множеств.ТогдаiDG [α] \ ∪mi=1 QG [α] = ∅.iДоказательство.

Предположим, что DG [α] \ ∪mi=1 QG [α] ̸= ∅. Значит суiществует хотя бы одна вершина v ∗ ∈ DG [α] \ ∪mi=1 QG [α], которая, очевидно,принадлежит и множеству DG [α]. По определению базового множества DG [α],содержащиеся в нем вершины несмежны с вершинами β и γ. Так как вершиныβ и γ так же несмежны, то множество Q = {v ∗ , β, γ} представляет собойнезависимое множество, следовательно, ∃ QkG [α] : Q ⊆ QkG [α].

Получаем, чтоiс одной стороны вершина v ∗ ∈ DG [α], а с другой — v ∗ ∈ Q ⊆ (∪mi=1 QG [α]),iтаким образом v ∗ не может принадлежать разности DG [α] \ ∪mi=1 QG [α]. Полу-чили противоречие, что и доказывает ошибочность предположения, согласноiкоторому DG [α] \ ∪mi=1 QG [α] ̸= ∅.Согласно теореме 1 и теореме 2, для того чтобы построить максимальные независимые множества, содержащие в себе некоторую пару α = (β, γ),необходимо использовать элементы базового множества для указанной пары.Что представляет собой базовое множество в матричном представлении графа?Рассмотрим пример.

Характеристики

Список файлов диссертации