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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

2. T
+
( x
2
) ∩ T
-
(x
2
) = { x
2
}. Следовательно, второй выделенный подграф G
2
состоит из одной вершины x
2
.
3. G'=G \ G
2
; G' = (X', A'); X' = { x
3
, x
4
, x
5
, x
6
, x
8
, x
9
, x
10
}.
4.Так как X' не пустое множество, то G' принимаем за G и процесс
разбиения продолжается.
РАЗБИЕНИЕ - 3.
1.Выберем, например, вершину x
3
(рис.22,в) T
+
( x
3
) = { x
3
, x
4
, x
5
, x
9
, x
10
}, T
-
( x
3
) = { x
3
, x
9
, x
10
}.
2.T
+
( x
3
) ∩ T
-
( x
3
) = { x
3
, x
9
, x
10
}. Следовательно, третий подграф G
3
состоит
из вершин x
3
, x
9
, x
10
, матрица смежности которого показана на рис.22 ,г.
x
1
x
7
x
1
1
x
1
1
A
1
=
x
7
1
x
2
x
3
x
4
x
5
x
6
x
8
x
9
x
10
T
+
(x
2
)
x
2
1 1 0
x
3
1 1 1 1
x
4
1 1
x
5
1
A= x
6
1 1
x
8
1
x
9
1
x
10
1 1 1
x
3
x
4
x
5
x
6
x
8
x
9
x
10
T
+
(x
3
)
x
3
1 1 1 1 0
x
4
1 1 1
x
5
1 2
А= x
6
11
x
8
x
9
1 1
x
10
1 1 1 1
T
-
(
)
0
1
2
x
3
x
9
x
10
x
3
1 1 1
A
3
=
x
9
1
1
x
4
x
5
x
6
x
8
T
+
(x
4
)
x
4
1 1 0
x
5
1 1
A =
x
6
1 1
x
8
x
4
x
5
A
4
=
x
4
1 1
x
5
1
Рис. 22. Пример разбиения: а)матрица смежности подграфа G
1
; б)
матрица смежности при 2-м разбиении; в) матрица смежности при 3-м
разбиении; г) матрица смежности подграфа G
3
; д) матрица смежности при
4-м разбиении; е) матрица смежности подграфа G
4
; 
        2. T+( x2 ) ∩ T- (x2) = { x2 }. Следовательно, второй выделенный подграф G2
состоит из одной вершины x2.
        3. G'=G \ G2; G' = (X', A'); X' = { x3, x4, x5, x6, x8, x9, x10 }.
        4.Так как X' не пустое множество, то G' принимаем за G и процесс
разбиения продолжается.
        РАЗБИЕНИЕ - 3.
        1.Выберем, например, вершину x3 (рис.22,в) T+( x3 ) = { x3, x4, x5, x9, x10}, T-( x3




                       x1 x7 x1                  x2   x3   x4       x5   x6       x8    x9 x10        T+(x2)
                                 1         x2    1                                1                     0
                 x1         1              x3         1    1                            1     1
           A1    x7              1         x4              1        1
           =                               x5              1
                                      A=   x6                            1        1
                                           x8                                                           1
                                           x9         1
                                           x10             1        1                   1

                        x3 x4 x5 x6 x8 x9 x10              T+(x3)
                 x3     1 1            1 1                   0
                 x4        1 1                               1
                                                                                            x3 x9 x10
                 x5        1                                 2
                                                                                 x3          1 1 1
        А=       x6              1 1
                                                                              A3 x9          1
                 x8                                                           =
                 x9     1                                       1                                 1
                 x10            1 1         1                   1

                T-( ) 0                     1    2
                      x4         x5   x6   x8          T+(x4                                x4 x5
                                                         )                    A4 x4         1 1
                 x4     1        1                       0                    =
                 x5     1                                1                             x5 1
         A=      x6                   1     1
                 x8

  Рис. 22. Пример разбиения: а)матрица смежности подграфа G1 ; б)
  матрица смежности при 2-м разбиении; в) матрица смежности при 3-м
  разбиении; г) матрица смежности подграфа G3; д) матрица смежности при
  4-м разбиении; е) матрица смежности подграфа G4;

) = { x3, x9, x10 }.
        2.T+( x3 ) ∩ T-( x3 ) = { x3, x9, x10 }. Следовательно, третий подграф G3 состоит
из вершин x3, x9, x10, матрица смежности которого показана на рис.22 ,г.

Страницы