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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

5. Для графа на рисунке найти сильные
компоненты, содержащие элементы x
1
и
x
5
.
Решение.
Т
+
(х
1
)={. . . . . . . . . . . . . .
.. . . . . . . . . . . . . . .
},
Т
-
(х
1
)={ . . . . . . . . . .
},
G
1
=Т
+
(х
1
) ∩ Т
-
(х
1
)= {
. . .
. . . . . . . },
Т
+
(х
5
)={ . . . . . . . . . . . . . . . . . .
},
Т
-
(х
5
)={ . . . . . . . . . . . . . . . . . .
},
G
2
=Т
+
(х
5
) ∩ Т
-
(х
5
)= { . . . . . . . . . .
}.
Х1
Х2 Х3 Х4 Х5 Х6 Х7 Х8
Х1 0 1 0 0 0 0 0 1
Х2 0 0 1 0 1 0 0 0
Х3 0 0 0 1 1 0 0 0
Х4 0 0 0 0 0 1 0 0
Х5 0 0 1 0 0 0 0 0
Х6 0 0 0 1 0 0 0 0
Х7 1 0 0 0 1 1 0 0
Х8 0 0 0 0 0 0 1 0
Х1
Х2 Х3 Х4 Х5 Х6 Х7 Х8 Т
+
(х
1
)
Х1 0 1 0 0 0 0 0 1
Х2 0 0 1 0 1 0 0 0
Х3 0 0 0 1 1 0 0 0
Х4 0 0 0 0 0 1 0 0
Х5 0 0 1 0 0 0 0 0
Х6 0 0 0 1 0 0 0 0
Х7 1 0 0 0 1 1 0 0
Х8 0 0 0 0 0 0 1 0
Т
-
(х
1
)
Х2 Х3 Х4 Х5 Х6 Т
+
(х
5
)
Х2 0 1 0 1 0
Х3 0 0 1 1 0
Х4 0 0 0 0 1
Х5 0 1 0 0 0
Х6 0 0 1 0 0
Т
-
(х
5
)
x
8
x
3
x
5
x
7
x
6
x
4
x
2
x
1 
5. Для графа на рисунке найти сильные
                                                                       x1                          x2
             Х2    Х3    Х4    Х5   Х6    Х7      Х8
       Х1
Х1 0        1    0   0    0    0           0      1
Х2 0        0    1   0    1    0           0      0                            x7          x5
                                                                x8                                           x3
Х3 0        0    0   1    1    0           0      0
Х4 0        0    0   0    0    1           0      0
Х5 0        0    1   0    0    0           0      0
                                                                                                             x4
Х6 0        0    0   1    0    0           0      0                         x6
Х7 1        0    0   0    1    1           0      0
Х8 0        0    0   0    0    0           1      0
компоненты, содержащие элементы x1        и x5.

                                          Решение.

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

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

Т-
(х5)

Страницы