Анализ графов на ЭВМ. Методические указания. Макарычев П.П - 8 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

8
графа G
1
, можно построить граф G
2
с меньшим числом элементов. В
группу входят операции удаления ребра или вершины, отождествления
вершин, стягивание ребра. Вторую группу составляют операции,
позволяющие строить графы с большим числом элементов. В группу
входят операции расщепления вершин, добавления ребра.
Отождествление вершин. В графе G
1
выделяются вершины и,v.
Определяют окружение Q
1
вершины u, и окружение Q
2
вершины v,
вычисляют их объединение Q = Q
1
∪ Q
2
. Затем над графом G
1
выполняются следующие преобразования:
— из графа G
1
удаляют вершины u, v (H
1
= G
1
- u - v);
— к графу Н
1
присоединяют новую вершину z (H
1
= H
1
+z);
— вершину z соединяют ребром с каждой из вершин w
1
∈Q
(G
2
= H
1
+ zw
i
, i = 1,2,3,…).
Стягивание ребра. Данная операция является операцией
отождествления смежных вершин и, v в графе G
1
.
Наиболее важными бинарными операциями являются: объединение,
пересечение, декартово произведение и кольцевая сумма.
Объединение. Граф G называется объединением или наложением
графов G
1
и G
2
, если V
G
= V
1
∪
V
2
; U
G
= U
1
∪
U
2
(рис. 1).
Рис. 1. Объединение графов G
1
, G
2
Объединение графов G
1
и G
2
называется дизъюнктным, если V
1
∩
V
2
=
∅
. При дизъюнктном объединении никакие два из объединяемых графов
не должны иметь общих вершин.
U
v
1
v
2
v
3
v
4
v
3
v
4
v
5
v
2
v
1
v
3
v
4
v
5 
графа G1, можно построить граф G2 с меньшим числом элементов. В
группу входят операции удаления ребра или вершины, отождествления
вершин,    стягивание     ребра.     Вторую         группу    составляют   операции,
позволяющие строить графы с большим числом элементов. В группу
входят операции расщепления вершин, добавления ребра.
      Отождествление вершин. В графе G1 выделяются вершины и,v.
Определяют окружение Q1 вершины u, и окружение Q2 вершины v,
вычисляют их объединение Q = Q1 ∪ Q2. Затем над графом G1
выполняются следующие преобразования:
          — из графа G1 удаляют вершины u, v (H1 = G1 - u - v);
          — к графу Н1 присоединяют новую вершину z (H1 = H1 +z);
          — вершину z соединяют ребром с каждой из вершин w1 ∈ Q
      (G2 = H1 + zwi, i = 1,2,3,…).
      Стягивание        ребра.     Данная          операция    является    операцией
отождествления смежных вершин и, v в графе G1.
      Наиболее важными бинарными операциями являются: объединение,
пересечение, декартово произведение и кольцевая сумма.
      Объединение. Граф G называется объединением или наложением
графов G1 и G2, если VG = V1 ∪ V2; UG = U1 ∪ U2 (рис. 1).
                  v2
                           v3        v3                  v2     v3

                                              v5                      v5
                                 U
                           v4        v4                          v4
                                                         v1
                   v1


                         Рис. 1. Объединение графов G1, G2
      Объединение графов G1 и G2 называется дизъюнктным, если V1 ∩ V2
= ∅ . При дизъюнктном объединении никакие два из объединяемых графов
не должны иметь общих вершин.




                                          8

Страницы