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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Решение.
Матрица смежности
Х
1
Х2 Х3 Х4 Х5 Х6 Х7 Х8 Т
+
(х
1
)
Х1 1 1 0 1 0 0 0 0
Х2 1 0 1 0 0 0 1 0
Х3 0 0 0 0 1 0 0 0
Х4 0 0 1 0 0 0 0 0
Х5 0 0 0 1 0 0 0 0
Х6 0 0 0 0 0 0 0 0
Х7 0 1 0 0 0 1 0 1
Х8 1 0 0 0 0 0 0 0
Т
-
(х
1
)
Т
+
(х
1
)={. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .
},
Т
-
(х
1
)={ . . . . . . . . . . . . . . . . . . .
},
G
1
=Т
+
(х
1
) ∩ Т
-
(х
1
) = {
. . . . . . . . . . . . . . }
Т
+
(х
3
)={ . . . . . . . . . . . . . . . . . . . . }
Т
-
(х
3
)={ . . . . . . . . . . . . . . . . . . . . }
G
2
=Т
+
(х
3
) ∩ Т
-
(х
3
)= { . . . . . . . . . . }
G
3
={ . . . . . . . . . . }
Результат разбиения:
. .
Х3 Х4 Х5 Х6 Т
+
(х
3
)
Х3 0 0 1 0
Х4 1 0 0 0
Х5 0 1 0 0
Х6 0 0 0 0
Т
-
(х
3
)
x
1
x
2
x
3
x
4
G
2
x
1
x
2
x
3
x
5
x
4
x
6
x
7
x
8
G
1
G
2
G
3
Рис.7.12 
                                                                    x2                x3
                                                G1                                                   G2
                                                          x1

                                                                                                x4

                                                     x8
                                                                                           x5
                                                               Решение.          x6
     Матрица смежности          x7
                                                                                      G3
               Х2 Х3 Х4 Х5 Х6 Х7 Х8                                          Т+(х1)
                Х
                                                               Рис.7.12
                1
     Х1         1      1      0        1        0     0        0    0
     Х2         1      0      1        0        0     0        1    0
     Х3         0      0      0        0        1     0        0    0
     Х4         0      0      1        0        0     0        0    0
     Х5         0      0      0        1        0     0        0    0
     Х6         0      0      0        0        0     0        0    0
     Х7         0      1      0        0        0     1        0    1
     Х8         1      0      0        0        0     0        0    0

     Т-(х1)
     Т+(х1)={. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . },
     Т-(х1)={ . . . . . . . . . . . . . . . . . . . },
     G1 =Т+(х1) ∩ Т-(х1) = { . . . . . . . . . . . . . . }
             Х3     Х4     Х5     Х6        Т+(х3)
     Х3      0      0      1      0
     Х4      1      0      0      0
     Х5      0      1      0      0
     Х6      0      0      0      0

     Т-
     (х3)

     Т+(х3)={ . . . . . . . . . . . . . . . . . . . . }
     Т-(х3)={ . . . . . . . . . . . . . . . . . . . . }
     G2 =Т+(х3) ∩ Т-(х3)= { . . . . . . . . . . }

     G3 ={ . . . . . . . . . . }

     Результат разбиения:

     .                                                                                                .
     x2                                    x3

x1                                                                  G2


                                                               x4

Страницы