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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Матрица смежности исходного графа
а) Матрица смежности порожденного подграфа
Х1
Х2 Х3 Х4 Х5
Х1
Х2
Х3
Х4
Х5
б) Матрица смежности остовного подграфа
Х1
Х2 Х3 Х4 Х5 Х6 Х7 Х8
Х1
Х2
Х3
Х4
Х5
Х6
Х7
Х8
в) Матрица смежности остовного порожденного
подграфа
Х1
Х2 Х3 Х4 Х5
Х1
Х2
Х3
Х4
Х5
3.3.Сильно связные графы и компоненты графа
Кроме классификации типов графов данной в п.3.1 графы могут быть
классифицированы по связности: сильно связные, односторонне связные, слабо
связные и несвязные.
Орграф называется
сильно связным или сильным, если для двух любых
различных его вершин x
i
и x
j
существует по крайней мере один путь,
Х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
x
3
x
5
x
4
x
2
x
1
x
8
x
3
x
5
x
7
x
6
x
4
x
2
x
1
x
3
x
5
x
4
x
2
x
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
а) Матрица смежности порожденного подграфа
            Х2 Х3 Х4 Х5
     Х1                                              x1              x2

Х1
Х2
Х3                                                              x5
                                                                          x3
Х4
Х5

б) Матрица смежности остовного подграфа                                   x4
            Х2 Х3 Х4 Х5 Х6 Х7 Х8
     Х1                                              x1              x2
Х1
Х2
Х3                                                              x5
                                                x8         x7
Х4                                                                        x3
Х5
Х6
Х7                                                                        x4
Х8                                                        x6

в) Матрица смежности остовного порожденного          x1              x2
подграфа
            Х2 Х3 Х4 Х5
     Х1                                                         x5
Х1                                                                        x3
Х2
Х3
Х4                                                                        x4
Х5
                3.3.Сильно связные графы и компоненты графа

      Кроме классификации типов графов данной в п.3.1 графы могут быть
классифицированы по связности: сильно связные, односторонне связные, слабо
связные и несвязные.
      Орграф называется сильно связным или сильным, если для двух любых
различных его вершин xi и xj     существует по крайней мере один путь,

Страницы