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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Легко убедиться в том, что три рассмотренные операции коммутативны т.е.
G
1
∪ G
2
= G
2
∪ G
1
, G
1
∩ G
2
= G
2
∩ G1, G
1
⊕ G
2
= G
2
⊕ G
1
, и многоместны ,
т.е. G1 ∩ G2 ∩ G3 ∩ G4∩ ... , G1 ∪ G2 ∪ G3 ∪ G4 ∪ ... и так далее.
Рассмотрим унарные операции на графе .
Удаление вершины. Если x
i
-вершина графа G=(X,A), то G-x
i
-
порожденный подграф графа G на множестве вершин X-x
i
,т.е. G-x
i
является
графом , получившимся после удаления из графа G вершины x
i
и всех ребер,
x
6
x
5
x
4
x
3
x
1
x
2
a
1
a
8
a
5
a
3
a
6
a
9
a
10
б)
x
6
x
5
x
4
x
3
x
1
x
2
a
1
a
2
a
5
a
4
a
3
a
6
a
7
а)
x
1
x
2
x
3
x
4
x
5
x
6
x
1
1 1
x
2
1
A
1
=
x
3
1 1 1 1
x
4
x
5
x
6
)
x
1
x
2
x
3
x
4
x
5
x
6
x
1
1 1 1
x
2
A
2
= x
3
1 1
x
4
1 1
x
5
x
6
г)
)
x
6
x
5
x
4
x
3
x
1
x
2
a
1
a
8
a
5
a
3
a
6
a
9
a
10
a
7
a
4
x
1
x
2
x
3
x
4
x
5
x
6
x
1
1 1 1
x
2
1
A
3
=x
3
1 1 1 1
x
4
1 1
x
5
x
6
е
)
д)
Рис. 6. Операция объединения:
а)граф G
1
; б)граф G
2
; в) матрица смежности графа G
1
; г) матрица
смежности графа G
2
;
д) G
1
∪ G
2
; е) матрица смежности графа G
3
. 
                            a1                       x2                                  a1
           x1                                                        x1                                           x2

               a5           a4                        a2                 a5                        a9             a8
                                     a3                                                           a3
           x3                                                        x3
                                                 x4                                                           x4
                a7                    a6
                                                                              a10                       a6

                     x5                         x6                            x5                             x6

                                 а)                                                               б)


                 x1 x2 x3 x4 x5                            x6
                                                                               x1 x2 x3 x4 x5 x6
          x1        1 1
                                                                     x1           1 1 1
          x2              1
                                                                     x2
     A1   x3        1     1 1                              1
                                                                 A2= x3                                 1              1
     =
                                                                     x4                   1                   1
          x4
                                                                     x5
          x5
                                                                     x6
          x6
                                                                                    г)
                                 )
                                                                                              )
                           a1                        x2
               x1          a9
           a5         a4                    a8                            x1 x2 x3 x4 x5 x6
                                     a3                             x1       1 1 1
          x3                                                        x2             1
                                                     x4         A3= x3       1     1 1 1
               a7 a10                      a6                       x4       1        1
                                                                    x5
                x5                              x6                  x6
                                     д)
                                                                                         е)

          Рис. 6. Операция объединения:
           а)граф G1 ; б)граф G2 ; в) матрица смежности графа G1; г) матрица
          смежности графа G2 ; д) G1 ∪ G2 ; е) матрица смежности графа G3.

      Легко убедиться в том, что три рассмотренные операции коммутативны т.е.
G1 ∪ G2 = G2 ∪ G1, G1 ∩ G2 = G2 ∩ G1, G1 ⊕ G2 = G2 ⊕ G1 , и многоместны ,
т.е. G1 ∩ G2 ∩ G3 ∩ G4∩ ... , G1 ∪ G2 ∪ G3 ∪ G4 ∪ ... и так далее.
Рассмотрим унарные операции на графе .
      Удаление вершины. Если xi-вершина             графа    G=(X,A), то  G-xi-
порожденный подграф графа G на множестве вершин X-xi ,т.е. G-xi является
графом , получившимся после удаления из графа G вершины xi и всех ребер,

Страницы