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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

9
Пересечение. Граф G называется пересечением графов G
1
, G
2
, если
V
G
= V
1
∩ V
2
и U
G
= U
1
∪ U
2
(риc.2). Операция "пересечения" записывается
следующим образом: G = G
1
∩
G
2
.
Рис.2. Пересечение графов G
1
, G
2
.
Декартово произведение. Граф G называется декартовым
произведением графов G
1
и G
2
если V
G
= V
1
×
V
2
—декартово произведение
множеств вершин графов G
1
, G
2
, а множество ребер U
c
задается
следующим образом: вершины (z
i
, v
k
) и (z
j
, v
l
) смежны в графе G тогда и
только тогда, когда z
i
= z
j
(i = j), a v
k
и v
l
смежны в G
2
или v
k
= v
l
(k = l),
смежны в графе G
1
(см. рис.3).
Рис. 3. Декартово произведение графов G
1
, G
2
Кольцевая сумма графов представляет граф, который не имеет
изолированных вершин и состоит из ребер, присутствующих либо в
первом исходном графе, либо во втором. Кольцевая сумма определяется
следующим соотношением: G = G
1
⊕
G
2
(рис.4).
X
z
1
z
2
v
1
v
3
v
2
z
1
v
1
z
1
v
2
z
1
v
3
z
2
v
1
z
2
v
2
z
2
v
3
∩
v
1
v
2
v
3
v
5
v
3
v
4
v
6
v
2
v
1
v
6
v
4
v
5
v
1
v
4
v
6
v
5
v
3
v
2 
      Пересечение. Граф G называется пересечением графов G1, G2, если
VG = V1 ∩ V2 и UG = U1 ∪ U2 (риc.2). Операция "пересечения" записывается
следующим образом: G = G1 ∩ G2.
                   v1          v2     v1               v2               v1          v2

                                     ∩
                   v3           v4    v3               v4               v3          v4



                   v5           v6   v5                v6              v5           v6



                           Рис.2. Пересечение графов G1, G2.
      Декартово         произведение.         Граф          G     называется               декартовым
произведением графов G1 и G2 если VG = V1 × V2 —декартово произведение
множеств вершин графов G1, G2, а множество ребер Uc задается
следующим образом: вершины (zi, vk) и (zj, vl) смежны в графе G тогда и
только тогда, когда zi = zj(i = j), a vk и vl смежны в G2 или vk = vl(k = l),
смежны в графе G1 (см. рис.3).
                   z1                                            z1v1        z1v2   z1v3

                                v1       v2       v3
                           X
                  z2
                                                                z2v1         z2v2   z2v3


                  Рис. 3. Декартово произведение графов G1, G2
      Кольцевая сумма графов представляет граф, который не имеет
изолированных вершин и состоит из ребер, присутствующих либо в
первом исходном графе, либо во втором. Кольцевая сумма определяется
следующим соотношением: G = G1 ⊕ G2 (рис.4).




                                              9

Страницы