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

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

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

На Рисунке 3 изображен граф G и соответствующаяему матрица смежности A. Множество Q = {2, 3, 5} является максимальнымнезависимым в этом графе.Как видно из Рисунка 4, все элементы подматрицы матрицы A, стоящейна пересечение строк и столбцов с номерами, соответствующими вершинам из37а)б)Рис. 3: Графическое (а) и матричное (б) представление графа G.множества Q, являются нулевыми. Таким образом, нахождение максимальныхнезависимых множеств в графе эквивалентно нахождению нулевых подматрицего матрицы смежности, стоящих на главной диагонали.Рис. 4: Нулевая подматрица, образованная пересечением строк и столбцов, с номерами,соответствующими вершинам из МНМ.По определению базового множества для пары вершин α = (2, 3) в графе Gполучим:DG [(2, 3)] = {d | ad,2 = 0 & ad,3 = 0, d ∈ {1, 2, 3, 4, 5}} = {2, 3, 5}.Это множество можно получить и другим способом.

Для 2-й и 3-й строчкиматрицы смежности построим множества h(2) и h(3), состоящие из номеров38столбцов, содержащих нули, в соответствующих строчках:h(2) = {1, 2, 3, 5},h(3) = {2, 3, 4, 5}.Пересечение этих множеств как раз и дает нам искомое базовое множествоDG [(2, 3)] = h(2) ∩ h(3) = {2, 3, 5}. Таким образом, пересечение строчек истолбцов матрицы A с номерами i ∈ h(2) ∩ h(3) соответствует матричномупредставлению базового множества DG [(2, 3)].

Следует отметить, что в ходетщательного изучения истории развития алгоритмов поиска МНМ подобнаяидея построения клики неориентированного графа в виде пересечения списковсмежности соответствующих пар вершин была обнаружена автором в работеДжонстона (Johnston) [46]. В работах других авторов развитие этой идеи небыло найдено. В данном примере базовое множество совпадает с максимальнымнезависимым множеством. Но так бывает далеко не всегда. Добавим к нашемуграфу G вершину 6, соединенную ребром только с вершиной 5.

На Рисунке 5изображен получившийся граф и соответствующая ему матрица смежности.б)а)Рис. 5: Расширенный граф G (a) и его матрица смежности (б).Если в матрице смежности выделить элементы базового множества дляпары (2, 3), то получим следующее:D[(2, 3)] = h(2) ∩ h(3) = {2, 3, 5, 6}.39Как видно из Рисунка 6 (а) подматрица, образованная элементами базового множества D[(2, 3)] не является нулевой: a5,6 = a6,5 = 1. Значит, базовое множество представляет собой объединение двух МНМ, которые можнополучить вычеркиванием из подматрицы A строчки и столбца с номером 5(получим первое МНМ Q = {2, 3, 6}) или строчки и столбца с номером 6(получим второе МНМ Q = {2, 3, 5}).

На Рисунке 6 (б) представлено базовоемножество D[(2, 3)] после удаления из него вершины 5.б)а)Рис. 6: Базовое множество D[(2, 3)] после удаления из него вершины 5.Для более наглядного представления нулевой подматрицы на главной диагонали, соответствующей МНМ Q = {2, 3, 6}, преобразуем исходную матрицусмежности A, используя перестановку рядов. Под перестановкой рядов в квадратной матрице A будем понимать соединение перестановки строк с такой жеперестановкой столбцов [1].Для того чтобы получить искомую нулевую подматрицу на главной диагонали, нужно переставить строчки и столбцы исходной матрицы A в соответствиис перестановкой π:π=1 2 3 4 5 62 3 6 1 4 5.40На Рисунке 7 (а) представлена матрица P , которая соответствует перестановке π, т. е.

для нее равенство π(i) = j означает, что в j-ой строчке на месте i-гостолбца стоит 1. Таким образом, в каждой строчке и каждом столбце матрицыP только одну позицию занимает единица, а все остальные – нули.Перестановка рядов эквивалентна тому, что сначала матрицу A умножаемслева на P T , а затем результат домножаем справа на P . На Рисунке 7 (б)представлена преобразованная матрица A = P T AP , в которой отчетливо виденнулевой блок 3 × 3 на диагонали в левом верхнем углу.а)б)Рис. 7: Перестановочная матрица P (а) и преобразованная A = P T AP (б).После рассмотрения матричной интерпретации базового множества покажем, каким образом из его элементов будут формироваться максимальные независимые множества.Но для начала определимся, по какому критерию будем выбирать ведущийэлемент (то есть пару вершин, для которых мы начнем строить максимальныенезависимые множества) α∗0 = (β∗0 , γ∗0 ).

Среди всех элементов α0 ∈ S[α∗−1 ]ведущим станет тот, для которого выполнено условие:|D[α∗0 ]| = maxα0 ∈S[α∗−1 ] |D[α0 ]|.41Это позволит в процессе формирования Q[α∗0 ] убрать как можно большеузлов дерева поиска, рассмотрение которых не может привести к построениюуникальных максимальных независимых множеств.По определению базового множества, D[α∗0 ] состоит из вершин, одновременноe1 ⊆ G0 ≡ G,не смежных как с β∗0 , так и с γ∗0 . Следовательно, подграф Gиндуцированный множеством вершин D[α∗0 ] ⊆ V , можно представить в следующем виде:e 1 = G′ ∪ G1 ,Gгде G′ = ({β∗0 }, ∅) ∪ ({γ∗0 }, ∅), а подграф G1 , индуцирован опорным множествомω[α∗0 ]. Учитывая тот факт, что граф G′ состоит из двух компонент связности,каждая из которых представляет собой 1-вершинный граф, любое максимальe1 ⊆ G0 можно представить в следуюное независимое множество в подграфе Gщем виде:QGe1 [α∗0 ] = {β∗0 } ∪ {γ∗0 } ∪ QG1 .Таким образом, задача поиска МНМ в графе G0 сводится к задаче поискаМНМ в подграфе G1 .

Мы можем уже выписать первые две вершины текущегоМНМ J = {β∗0 , γ∗0 }.Рассматривая подграф G1 , действуем по той же схеме:– формируем множество S[α∗0 ] всех несмежных пар подграфа G1 , индуцированного опорным множеством ω[α∗0 ] (напомним, что опорное множество длянекоторого узла α = (β, γ) отличается от базового того же узла, отсутствием внем вершин β и γ);– среди элементов множества S[α∗0 ] выбираем тот узел α∗1 , для котороговыполнено условие:|D[α∗1 ]| = maxα1 ∈S[α∗0 ] |D[α1 ]|;– для выбранного узла α∗1 = (β∗1 , γ∗1 ) строим подграф G2 , индуцированныйопорным множеством ω[α∗1 ];42Рис. 8: Дерево поиска по алгоритму AllIS.– пополняем независимое множество:J = J ∪ {β∗1 , γ∗1 } = {β∗0 , γ∗0 , β∗1 , γ∗1 },и переходим к формированию МНМ в пографе G2 (см.

Рисунок 8).Так последовательно мы будем спускаться вниз по ветке дерева поиска.Каждый раз при формировании нового подграфа Gk+1 ⊂ Gk ⊂ . . . ⊂ G1 ⊂ G0возможны следующие случаи:1) ω[α∗k ] ̸= ∅, S[α∗k ] ̸= ∅, ∆[α∗k ] = ∅;2) ω[α∗k ] = ∅;3) ω[α∗k ] ̸= ∅, S[α∗k ] = ∅, ∆[α∗k ] ̸= ∅;4) ω[α∗k ] ̸= ∅, S[α∗k ] ̸= ∅, ∆[α∗k ] ̸= ∅.Рассмотрим каждый из этих случаев подробнее.1) Если опорное множество ω[α∗k ] не пусто, и из его вершин можно сформировать множество несмежных пар S[α∗k ], значит, мы имеем возможностьрасширить текущее независимое множество J путем добавления к нему одногоиз узлов α∗k+1 ∈ S[α∗k ], тем самым спустившись на новый уровень дерева поиска(Рисунок 9).43Рис.

9: Случай четного количества вершин в максимальном независимом множестве.2) Случай, когда опорное множество ω[α∗k ] пусто, говорит нам о том, чтопроцесс построения текущей ветви дерева поиска закончен, так как подграф,порожденный опорным множеством ω[α∗k ] представляет собой пустой граф. Покажем, что текущее независимое множество J, полученное по алгоритму, в этомслучае является максимальным независимым.На каждом уровне дерева поиска для расширения множества J использовались только пары вершин, следовательно, J состоит из четного количествавершин (Рисунок 9):J = {β∗0 , γ∗0 , β∗1 , γ∗1 , .

. . , β∗k , γ∗k }.Покажем, что все вершины из множества J попарно несмежны. Очевидно,что любая пара (β∗i , γ∗i ), i = 0, . . . , k представляет собой пару несмежных вершин.Вершины β∗1 , γ∗1 ∈ ω[α∗0 ], следовательно, не имеют ребер с вершинами β∗0 , γ∗0 .Аналогично, β∗2 , γ∗2 ∈ ω[α∗1 ] ⊂ ω[α∗0 ], и потому, не имеют ребер с вершинамиβ∗0 , γ∗0 , β∗1 , γ∗1 .

Таким образом для любой пары (β∗i , γ∗i ), i = 1, . . . , k справедливоследующее:β∗i , γ∗i ∈ ω[α∗i−1 ] ⊂ ω[α∗i−2 ] ⊂ . . . ⊂ ω[α∗1 ] ⊂ ω[α∗0 ],44следовательно, вершины β∗i , γ∗i , i = 1, . . . , k попарно несмежны с вершинамиβ∗i−1 , γ∗i−1 , β∗i−2 , γ∗i−2 , . . . , β∗1 , γ∗1 , β∗0 , γ∗0 .Покажем теперь, что множество J является максимальным независимым.Предположим, что это не так, значит, в графе G = (V, SV,A ) должна существовать хотя бы одна вершина v ∈ V , такая что множество Je = J ∪ {v} так жебудет являться независимым.

Так как по определению независимого множестваe то однавершина v одновременно несмежна со всеми вершинами из множества J,должна содержаться в каждом базовом множестве D[α∗i ], i = 0, . . . , k. Учитываятот факт, что v ∈ D[α∗k ], имеем, что ω[α∗k ] = D[α∗k ] \ {β∗k , γ∗k } = {v, . . .} ̸= ∅.Полученное противоречие доказывает тот факт, что ко множеству J нельзядобавить ни одну вершину с сохранением независимости, и следовательно, Jявляется максимальным независимым множеством.3) Попадание в ситуацию, когда ω[α∗k ] ̸= ∅, S[α∗k ] = ∅, ∆[α∗k ] ̸= ∅, такжеговорит о том, что построение ветви дерева поиска закончено. В отличие отпредыдущего случая, множество J будет состоять из нечетного количестваэлементов (Рисунок 10).Рис.

10: Случай нечетного количества вершин в максимальном независимом множестве.45Кроме этого количество самих МНМ, которые можно построить в даннойситуации, зависит от количества вершин во множестве ∆[α∗k ]. Действительно,множество вершин ∆[α∗k ] в подграфе Gk+1 , индуцированном множеством вершинω[α∗k ], представляет собой клику. Следовательно, для того, чтобы расширитьтекущее независимое множество J мы будем использовать не пару вершин (таккак S[α∗k ] = ∅), а только одну из вершин множества ∆[α∗k ].

Причем добавлениелюбой вершин δ ∈ ∆[α∗k ] позволит получить МНМ, следовательно, получимпоследовательность таких множеств:J = {β∗0 , γ∗0 , β∗1 , γ∗1 , . . . , β∗k , γ∗k , δ}, ∀δ ∈ ∆[α∗k ]Покажем, что все полученные множества J являются максимальными независимыми. Рассмотрим одно из них:J = {β∗0 , γ∗0 , β∗1 , γ∗1 , . . . , β∗k , γ∗k , δ},δ ∈ ∆[α∗k ].Независимость его доказывается так же, как и предыдущем случае. Предположим, что J независимое, но не максимальное независимое множество. В такомслучае, в графе G = (V, SV,A ) должна существовать хотя бы одна вершинаv ∈ V , такая что множество Je = J ∪ {v} так же будет являться независимым.Так как по определению независимого множества вершина v одновременноe то одна должна содержаться внесмежна со всеми вершинами из множества J,каждом базовом множестве D[α∗i ], i = 0, . .

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

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