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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

3. G' = G \ G
3
; G' = (X', A'); X' = { x
4
, x
5
, x
6
, x
8
}.
4. X'
≠∅, следовательно, процесс разбиения продолжаем: G' →G. X' →X.
РАЗБИЕНИЕ - 4.
1. Выберем x
4
∈X (рис.22,д) T
+
( x
4
) = { x
4
, x
5
}; T
-
( x
4
) = { x
4
, x
5
).
2.T
+
( x
4
) ∩T
-
( x
4
) = { x
4
, x
5
}, G
4
= (X
4
, A
4
); X
4
= { x
4
, x
5
}, матрица смежности A
4
показана на рис.22 ,е.
3. G' = G \ G
4
; G' = (X', A'); X' = { x
6
, x
8
}.
4. X'
≠ ∅, следовательно, переходим к пятому разбиению.
РАЗБИЕНИЕ - 5.
1. Выберем x
6
. T
+
( x
6
) = { x
6
, x
8
}; T
-
( x
6
) = { x
6
}.
2. T
+
( x
6
) ∩ T
-
( x
6
) = { x
6
}; G
5
= ( X
5
, A
5
); X
5
= { x
6
}.
3. G' = G \ G
5
; X' = { x
8
}.
4. X'
≠∅, но состоит из одной вершины, поэтому очевидно, что шестой
подграф содержит вершину x
8
. На этом процесс разбиения завершается. Итак,
результат разбиения:
G
1
=( X
1
, A
1
), X
1
= { x
1
, x
7
, x
11
}, G
2
= ( X
2
, A
2
), X
2
= { x
2
},
G
3
= ( X
3
, A
3
), X
3
= { x
3
, x
9
, x
10
}, G
4
= ( X
4
, A
4
), X
4
= { x
4
, x
5
},
G
5
= ( X
5
, A
5
), X
5
= { x
6
}, G
6
= ( X
6
, A
6
), X
6
= { x
8
}
показан на рис.23,а, где каждый подграф G
1, ... ,
G
6
представляет собой сильную
компоненту графа. Граф G* =(X* ,A* ) , в котором в качестве элементов выступают
сильные компоненты называется
конденсацией.(рис.23,б).
Подробная блок-схема алгоритма разбиения приведена в приложении 4.
. Упражнения 4.1 .
1. Методом Мальгранжа разбить граф, данный на рисунке, на подграфы.
G
3
x
10
x
9
x
3
G
2
x
2
G
1
x
1
x
7
x
11
x
6
G
5
G
6
x
8
x
4
x
5
G
4
G
3
G
4
G
5
G
1
G
2
G
6
а)
б)
Рис. 23. а)результат разбиения; б)конденсация
        3. G' = G \ G3; G' = (X', A'); X' = { x4, x5, x6, x8 }.
         4. X' ≠∅, следовательно, процесс разбиения продолжаем: G' →G. X' →X.
        РАЗБИЕНИЕ - 4.
        1. Выберем x4 ∈X (рис.22,д) T+ ( x4 ) = { x4, x5 }; T- ( x4 ) = { x4, x5 ).
        2.T+( x4 ) ∩T-( x4 ) = { x4, x5 }, G4 = (X4, A4); X4 = { x4, x5 }, матрица смежности A4
показана на рис.22 ,е.
        3. G' = G \ G4; G' = (X', A'); X' = { x6, x8 }.
        4. X' ≠ ∅, следовательно, переходим к пятому разбиению.
        РАЗБИЕНИЕ - 5.
        1. Выберем x6. T+ ( x6 ) = { x6, x8 }; T-( x6 ) = { x6 }.
        2. T+ ( x6 ) ∩ T- ( x6 ) = { x6 }; G5 = ( X5, A5 ); X5 = { x6 }.
        3. G' = G \ G5; X' = { x8 }.
        4. X'≠∅, но состоит из одной вершины, поэтому очевидно, что шестой
    подграф содержит вершину x8. На этом процесс разбиения завершается. Итак,
    результат разбиения:
        G1 =( X1, A1 ), X1 = { x1, x7, x11 },                 G2 = ( X2, A2 ), X2 = { x2 },
        G3 = ( X3, A3 ), X3 = { x3, x9, x10 },                 G4 = ( X4, A4 ), X4 = { x4, x5 },
        G5 = ( X5, A5 ), X5 = { x6 },                G6 = ( X6, A6 ), X6 = { x8 }
показан на рис.23,а, где каждый подграф G1,                        ... ,G6   представляет собой сильную
компоненту графа. Граф G* =(X* ,A* ) , в котором в качестве элементов выступают

                          G3
                         x9                         G2
                                                         x2
               x3        x10    G1                                                         G2
                                    x1                                       G3
                                                                                    G1
                               x7             x11                                                   G6
                                                                       G4
          x4             x5                                                         G5
                                         x6         x8
                    G4                                                                б)
                                         G5         G6
                                         а)
               Рис. 23. а)результат разбиения; б)конденсация

сильные компоненты называется конденсацией.(рис.23,б).
Подробная блок-схема алгоритма разбиения приведена в приложении 4.
.        Упражнения 4.1                                                                         .
1. Методом Мальгранжа разбить граф, данный на рисунке, на подграфы.

Страницы