Диссертация (1149246), страница 9
Текст из файла (страница 9)
26: Граф, индуцированный опорным множеством ω[α∗k ] = {δ1 , δ2 , δ3 , δ4 , δ5 } при значении|S[α]| =m(m−1)2− 2 и трем различным вершинам, инцидентным двум ребрам (а) и призначении |S[α]| =m(m−1)2− 2 и четырем различным вершинам, инцидентным двум ребрам(б).Если количество различных вершин равно трем, значит, необходимо проверить условие: |D[α∗k ]| + 2k − 1 > |Qmax |. В случае его выполненияQmax = {β∗0 , γ∗0 , β∗1 , γ∗1 , ..., β∗k−1 , γ∗k−1 } ∪ (ω[α∗k ] \ {δ}),где вершина δ инцидентна обоим ребрам. В противном случае отказываемсяот текущего узла α∗k и переходим к выбору нового ведущего элемента на k-муровне.Если же количество различных вершин равно четырем, то при выполненииусловия |D[α∗k ]| + 2k − 2 > |Qmax | наибольшим независимым множеством будет69Qmax = {β∗0 , γ∗0 , β∗1 , γ∗1 , ..., β∗k−1 , γ∗k−1 } ∪ (ω[α∗k ] \ {δ1 , δ2 }), где вершины δ1 и δ2инцидентны разным ребрам.
Иначе вновь переходим к выбору ведущего элемента k-го уровня.§3. Пример построения наибольшего независимогомножестваДля графа, заданного матрицей смежности A (Рисунок 27), множество вершин V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, множество несмежных парSV,A = {(1, 2), (1, 3), (1, 6), (1, 9), (1, 10), (2, 3), (2, 6), (2, 9), (2, 10), (3, 4),(3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9),(4, 10), (5, 6), (5, 7, (5, 8), (5, 9), (5, 10), (7, 8), (7, 9), (8, 9), (8, 10)}.Рис. 27: Матрица смежности графа G.В начале работы алгоритма MaxIS уровень дерева поиска k = 0, текущеенаибольшее независимое множество Qmax = ∅. Опорное множество ω[α∗−1 ] ≡ V ,где α∗−1 – некоторый абстрактный узел, состоящий из вершин, изолированныхот всех вершин рассматриваемого графа, множество S[α∗−1 ] ≡ SV,A .Формируем базовые множества нулевого уровня для всех несмежных парграфа (Таблица 1):D[α0 ] = {d ∈ ω[α∗−1 ] | (d, β 0 ) ∈ S[α∗−1 ] & (d, γ 0 ) ∈ S[α∗−1 ]} ∪ {β 0 , γ 0 }.70Таблица 1.α0D[α0 ](1,2), (1,3){1, 2, 3, 6, 9, 10}|D[α0 ]|6(1,6), (1,10) {1, 2, 3, 6, 10}5(1,9), (2,9){1, 2, 3, 9}4(2,3){1, 2, 3, 6, 9, 10}6(2,6), (2,10) {1, 2, 3, 6, 10}5(3,4), (3,5){3, 4, 5, 6, 7, 8, 9, 10}8(3,6){1, 2, 3, 4, 5, 6, 8, 10}8(3,7){3, 4, 5, 7, 8, 9}6(3,8), (4,5){3, 4, 5, 6, 7, 8, 9, 10}8(3,9){1, 2, 3, 4, 5, 7, 8, 9}8(3,10){1, 2, 3, 4, 5, 6, 8, 10}8(4,6){3, 4, 5, 6, 8, 10}6(4,7), (4,9){3, 4, 5, 7, 8, 9}6(4,8){3, 4, 5, 6, 7, 8, 9, 10}8(4,10), (5,6) {3, 4, 5, 6, 8, 10}6(5,7), (5,9){3, 4, 5, 7, 8, 9}6(5,8){3, 4, 5, 6, 7, 8, 9, 10}8(5,10), (6,8) {3, 4, 5, 6, 8, 10}6(6,10){1, 2, 3, 4, 5, 6, 8, 10}8(7,8), (7,9){3, 4, 5, 7, 8, 9}6(8,9){3, 4, 5, 7, 8, 9}6(8,10){3, 4, 5, 6, 8, 10}6Текущее значение переменной continue равно true, поэтому проверяем условие S[α∗k−1 ] = ∅.
Так как S[α∗−1 ] ≡ SV,A ̸= ∅, то выбираем ведущий элементα∗0 = (β∗0 , γ∗0 ) ∈ S[α∗−1 ] : |D[α∗0 ]| = maxα0 ∈S[α∗−1 ] D[α0 ]. Для выбранного узла71α∗0 = (3, 4) выполняем проверку на целесообразность дальнейшего поиска вэтом направлении. Если |D[α∗k ]| + 2k > |Qmax |, то есть возможность построитьмаксимальное независимое множество большей мощности, чем то, что уже имеется.Для выбранного узла α∗0 = (3, 4) условие |D[α∗k ]| + 2k > |Qmax | выполняется,так как, 8 + 2 ∗ 0 = 8 > 0. Строим для него опорное множествоω[(3, 4)] = D[(3, 4)] \ {3, 4} = {5, 6, 7, 8, 9, 10}.Мощность опорного множества больше единицы, а значит, можно сформироватьмножество S[α∗k ] при k = 0.
По определению,S[α∗0 ] = {(p, q) | (p, q) ∈ ω[α∗0 ][2] & ap,q = 0, p, q ∈ ω[α∗0 ]},следовательно, S[(3, 4)] = {(5, 6), (5, 7), (5, 8), (5, 9), (5, 10), (6, 8), (6, 10), (7, 8),(7, 9), (8, 9), (8, 10)}. Множество S[α∗0 ] ̸= ∅ и состоит из 11 пар, поэтому продолжаем формировать ветку дерева поиска, идущую из узла α∗0 = (3, 4).Для всех несмежных пар множества S[(3, 4)] формируем базовые множествапервого уровня (Таблица 2). Выбираем ведущий элемент α∗1 = (5, 8) ∈ S[(3, 4)],для которого базовое множество имеет наибольшую мощность: |D[(5, 8)]| = 6.В силу выполнения условия:|D[(5, 8)]| + 2k = 6 + 2 ∗ 1 = 8 > |Qmax |,формируем множество ω[(5, 8)] = D[(5, 8)] \ {5, 8} = {6, 7, 9, 10}.Мощность опорного множества больше единицы, продолжаем спускаться науровень ниже и формируем множество S[α∗1 ]:S[(5, 8)] = {(6, 10), (7, 9)}.Далее выбираем следующий ведущий элемент:α∗2 = (6, 10) ∈ S[(5, 8)], |D[6, 10]| = 2,72для которого базовое множество в Таблице 3 имеет максимальную мощность,кроме этого |D[(6, 10)] + 2k = 6 + 2 ∗ 1 = 8 > |Qmax |.Таблица 2.|D[α1 ]|α1D[α1 ](5,6){5, 6, 8, 10}4(5,7){5, 7, 8, 9}4(5,8){5, 6, 7, 8, 9, 10}6(5,9){5, 7, 8, 9}4(5,10) {5, 6, 8, 10}4(6,8){5, 6, 8, 10}4(6,10) {5, 6, 8, 10}4(7,8){5, 7, 8, 9}4(7,9){5, 7, 8, 9}4(8,9){5, 7, 8, 9}4(8,10) {5, 6, 8, 10}4Таблица 3.α2D[α2 ]|D[α2 ]|(6,10) {6, 10}2(7,9)2{7, 9}Выполнение условия ω[(6, 10)] = ∅ означает, что мы полностью построиливетку дерева поиска, идущую из узла α∗0 = (3, 4):Qmax = {3, 4, 5, 6, 8, 10}.Проверяем возможность удаления некоторых элементов из множества S[α∗1 ],используя множество R[α∗2 ].
Среди элементов α2 ∈ S[α∗1 ] нет таких, для которыхD[α2 ] ⊆ D[α∗2 ], поэтому множество R[α∗2 ] = ∅. Убираем из множества S[(5, 8)]только рассмотренный узел α∗2 = (6, 10). Полученное множество S[α∗1 ] ̸= ∅,поэтому выбираем ведущий элемент второго уровня: α∗2 = (7, 9), D[α∗2 ] = 2. Так73как для выбранного узла α∗2 = (7, 9) условие перспективности продвижения повыбранной ветке не выполняется:|D[(7, 9)]| + 2 ∗ 2 = |Qmax |,то продолжение дальнейшего продвижения на базе выбранного набора узловне позволит построить МНМ большей мощности, чем Qmax . Возвращаемся напредыдущий уровень (k = k − 1) и рассматриваем множество: S[α∗0 ] = S[(3, 4)].Среди элементов α1 ∈ S[α∗0 ] нет таких, для которых D[α1 ] ⊆ D[α∗1 ], поэтомуубираем из множества S[(3, 4)] только рассмотренный узел α∗1 = (5, 8):S[(3, 4)] = S[(3, 4)] \ {(3, 4)}.Полученное множество S[α∗0 ] ̸= ∅, снова выбираем ведущий элемент первогоуровня.
Пусть α∗1 = (5, 6), |D[α∗1 ]| = 4. Для выбранного узла α∗1 = (5, 6) условиеперспективности продвижения по выбранной ветке не выполняется, так как|D[(5, 6)]| + 2 ∗ 1 = |Qmax |.Возвращаемся на предыдущий уровень (k = k − 1) и рассматриваем множествоS[α∗−1 ] = SV,A .Из элементов α0 ∈ S[α∗−1 ] таких, что |D[α0 ]|+2∗0 > |Qmax |, выбираем те, длякоторых выполняется условие D[α0 ] ⊆ D[α∗0 ]. Выбранные элементы записываемво множество R[α∗0 ]:R[α∗0 ] = {(3, 5), (3, 8), (4, 5), (4, 8), (5, 8)}.Исключаем из множества S[α∗−1 ] множество элементов R[α∗0 ] и рассмотренныйузел α∗0 = (3, 4):S[α∗−1 ] = {(1, 2), (1, 3), (1, 6), (1, 9), (1, 10), (2, 3), (2, 6), (2, 9), (2, 10),(3, 6), (3, 7), (3, 9), (3, 10), (4, 6), (4, 7), (4, 9), (4, 10), (5, 6), (5, 7),(5, 9), (5, 10), (6, 8), (6, 10), (7, 8), (7, 9), (8, 9), (8, 10)}.74В качестве ведущего элемента на нулевом уровне выбирается узелα∗0 = (3, 6) : |D[(3, 6)]| = max−1 |D[α0 ]| = 8.α0 ∈S[α∗ ]Так как условие перспективности для выбранного узла выполняется:|D[(3, 6)]| + 2 ∗ 0 = 8, |Qmax | = 6,то начинаем формировать опорное множество:ω[(3, 6)] = D[(3, 6)] \ {3, 6} = {1, 2, 4, 5, 8, 10}.Мощность опорного множества больше единицы, поэтому переходим на следующий уровень (k = k + 1) и формируем множество S[α∗0 ]:S[(3, 6)] = {(1, 2), (1, 10), (2, 10), (4, 5), (4, 8), (4, 10), (5, 8), (5, 10), (8, 10)}.Для всех несмежных пар множества S[(3, 6)] строим базовые множества первогоуровня (Таблица 4).Таблица 4.α1D[α1 ]|D[α1 ]|(1,2){1, 2}2(1,10) {1,2,10}3(2,10) {1,2,10}3(4,5){4,5,8,10}4(4,8){4,5,8,10}4(4,10) {4,5,8,10}4(5,8){4,5,8,10}4(5,10) {4,5,8,10}4(8,10) {4,5,8,10}4Выбираем в качестве ведущего элемента на первом уровне узелα∗1 = (4, 5): |D[(4, 5)]| = maxα1 ∈S[α∗0 ] |D[α1 ]| = 4.
Так как условие перспектив-75ности дальнейшего продвижения по ветви, идущей из выбранного узла, не выполняется:|D[(4, 5)]| + 2 ∗ 1 = 6, |Qmax | = 6,то возвращаемся на один уровень выше (k = k −1) и приступаем к исключениюэлементов из множества S[α∗−1 ].Из элементов α0 ∈ S[α∗−1 ] таких, что |D[α0 ]| + 2 ∗ 0 > |Qmax |, выбираемте, для которых выполняется условие: D[α0 ] ⊆ D[α∗0 ]. Выбранные элементызаписываем во множество R[α∗0 ]:D[α∗0 ] = D[(3, 6)] = {1, 2, 3, 4, 5, 6, 8, 10}, R[α∗0 ] = {(3, 10), (6, 10)}.Исключаем из множества S[α∗−1 ] множество элементов R[α∗0 ] и рассмотренныйузел α∗0 = (3, 6):S[α∗−1 ] = {(1, 2), (1, 3), (1, 6), (1, 9), (1, 10), (2, 3), (2, 6), (2, 9), (2, 10),(3, 7), (3, 9), (4, 6), (4, 7), (4, 9), (4, 10), (5, 6), (5, 7), (5, 9),(5, 10), (6, 8), (7, 8), (7, 9), (8, 9), (8, 10)}.В качестве ведущего элемента на нулевом уровне выбирается узелα∗0 = (3, 9) : |D[(3, 9)]| = max−1 |D[α0 ]| = 8.α0 ∈S[α∗ ]Выполнение условия перспективности для выбранного узла:|D[(3, 9)]| + 2 ∗ 0 = 8, |Qmax | = 6,позволяет начать формирование новой ветки дерева поиска, идущей из этогоузла.
Формируем для него опорное множество:ω[(3, 9)] = D[(3, 9)] \ {3, 9} = {1, 2, 4, 5, 7, 8},и переходим на следующий уровень k = k + 1.76Множество S[(3, 9)] = {(1, 2), (4, 5), (4, 7), (4, 8), (5, 7), (5, 8), (7, 8)}. Для всехнесмежных пар множества S[(3, 9)] формируем базовые множества первого уровня (Таблица 5).Таблица 5.α1D[α1 ]|D[α1 ]|(1,2){1, 2}2(4,5), (4,7), (4,8) {4,5,7,8}4(5,8), (7,8)4{4,5,7,8}Выбираем в качестве ведущего элемента на первом уровне узелα∗1 = (4, 5): |D[(4, 5)]| = maxα1 ∈S[α∗0 ] |D[α1 ]| = 4.
Так как условие перспективности для выбранного узла не выполняется:|D[(4, 5)]| + 2 ∗ 1 = 6, |Qmax | = 6,то формирование МНМ, содержащих вершины 4 и 5, прекращается. Возвращаемся на предыдущий уровень и приступаем к исключению элементов измножества S[α∗−1 ]. Среди элементов α0 ∈ S[α∗−1 ] нет таких, что|D[α0 ]| + 2 ∗ 0 > |Qmax |,поэтому R[α∗0 ] = ∅ и из множества S[α∗−1 ] исключаем только рассмотренныйузел α∗0 = (3, 9):S[α∗−1 ] = {(1, 2), (1, 3), (1, 6), (1, 9), (1, 10), (2, 3), (2, 6), (2, 9), (2, 10),(3, 7), (4, 6), (4, 7), (4, 9), (4, 10), (5, 6), (5, 7), (5, 9), (5, 10),(6, 8), (7, 8), (7, 9), (8, 9), (8, 10)}.После исключения из множества S[α∗−1 ] последнего элемента, для которогомощность базового множества равна восьми, в нем остались элементы, которыене могут дать МНМ большей мощности, чем то, что уже построено:∀α0 ∈ S[α∗−1 ] |D[α0 ]| + 2 ∗ 0 ≤ |Qmax |.77Так как k = 0, переменная continue принимает значение false, то алгоритмзаканчивает свою работу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
