Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 44 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

4. МЕТОДЫ РАЗБИЕНИЯ ГРАФА НА МАКСИМАЛЬНЫЕ СИЛЬНО
СВЯЗНЫЕ ПОДГРАФЫ .
4.1 МЕТОД МАЛЬГРАНЖА
Пусть дан граф
G=(X, A), где X={ x
i
}, i =1, 2, ... , n – множество вершин,
а
A={ a
i
}, i =1, 2, ..., m – где множество дуг, описанных матрицей смежности.
Алгоритм разбиения заключается в следующем [4].
а
1. Для произвольной вершины
x
i
∈ X находим прямое T
+
(x
i
) и обратное
T
–
(x
i
) транзитивные замыкания.
2. Находим
T
+
(x
i
) ∩ T
–
(x
i
) . Множество вершин этого пересечения
составляют вершины максимального сильно связного подграфа G
1
= (X
1
, A
1
) .
3. Из исходного графа вычитаем подграф
G
1
:G '=G\G
1
, Х=X\X
1
.
4. Граф
G ' принимаем за исходный граф и пока X ' ≠ ∅ пункты 1, 2, 3
алгоритма повторяются.
Рассмотрим этот алгоритм более подробно на примере разбиения
графа, представленного на рис. 21,
a, матрица смежности которого показана
на рис. 21,
б.
РАЗБИЕНИЕ - 1 .
1. Начальной вершиной первого разбиения выберем x
1
. Построим прямое и
обратное транзитивные замыкания. T
+
(x
1
) - столбец показан справа от матрицы А,
а T
-
(x
1
)- строка, находящаяся ниже матрицы смежности.
T
+
( x
1
) = {x
1
, x
4
, x
5
, x
6
, x
7
, x
8
, x
11
}
T
-
( x
1
) = {x
1
, x
2
, x
3
, x
7
, x
9
, x
10
, x
11
}
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
10
x
11
T(x
1
)
x
1
1 0
x
2
1 1 1 1
x
3
1 1 1 1
x
4
1 1 4
x
5
1 3
x
6
1 1 3
x
7
1 1
x
8
4
x
9
1
x
10
1 1 1 1
x
11
1 1 1 1 2
T
–
(x
1
) 0 1 2 2 3 1 1
Б
Рис. 21 
    4. МЕТОДЫ РАЗБИЕНИЯ ГРАФА НА МАКСИМАЛЬНЫЕ СИЛЬНО
                                  СВЯЗНЫЕ ПОДГРАФЫ .
                                4.1 МЕТОД МАЛЬГРАНЖА
      Пусть дан граф G=(X, A), где X={ xi }, i =1, 2, ... , n – множество вершин,
а A={ ai }, i =1, 2, ..., m – где множество дуг, описанных матрицей смежности.
Алгоритм разбиения заключается в следующем [4].




                                                   а


                x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11           T(x1)
       1.1Для произвольной вершины xi ∈ X находим прямое T0 +(xi) и обратное
        x                             1
        x2      1 1 замыкания.
T–(xi) транзитивные                      1           1
        x3            1 1                    1 1
       2.x4 Находим T+(xi)1 ∩ 1T–(xi) . Множество вершин этого 4   пересечения
составляют
        x5    вершины максимального
                          1                                    3 G1 = (X1, A1) .
                                        сильно связного подграфа
       3.x6Из исходного графа вычитаем
                                 1       1подграф G1:G '=G\G1, Х=
                                                               3 X\X1.
        x7                                           1         1
       4. Граф G ' принимаем за исходный граф и пока X ' ≠ ∅ пункты 1, 2, 3
        x8                                                     4
алгоритма
        x9 повторяются.
                      1
       Рассмотрим
        x10     1    этот 1алгоритм
                              1        более 1подробно на примере разбиения
графа, xпредставленного
          11    1          на рис.
                              1 1 21,a, матрица смежности
                                                     1      которого
                                                               2       показана
на рис. 21,б.
       T–(x1) 0      1    2                   2        3   1   1

      РАЗБИЕНИЕ - 1 .           Б
                              Рис. 21разбиения выберем x1. Построим прямое и
      1. Начальной вершиной первого
обратное транзитивные замыкания. T+(x1) - столбец показан справа от матрицы А,
а T- (x1)- строка, находящаяся ниже матрицы смежности.
      T+ ( x1) = {x1, x4, x5, x6, x7, x8, x11 }
      T- ( x1 ) = {x1, x2, x3, x7, x9, x10, x11}

Страницы