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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

X
4
0 0 0 0 0 0 -1 -1 1 0
X
5
0 0 0 0 0 0 0 0 -1 -1
X
6
0 0 0 0 0 1 0 0 0 1
Матрица смежности
X
1
X
2
X
3
X
4
X
5
X
6
X
1
X
2
X
3
X
4
X
5
X
6
. .
1.3 Операции над графами
Рассмотрим семь операций над графами, три из которых являются
бинарными, включающими два графа, а остальные четыре - унарные, то есть
определены на одном графе.
Исходные графы G
1
и G
2
показаны на рис. 6, а,б. G
1
=(X
1
, A
1
), где X
1
={x
i
},
i=1,2,...,6, A={ a
i
}, i=1,2,...,7. и G
2
=(X
2
, A
2
), где X
2
={ x
i
}, i=1,2,...,6, A={a
1
, a
3
, a
5
, a
6
, a
9
,
a
10
}. Матрицы смежности графов показаны на рис.6,в и 6,г соответственно.
(Чтобы не загромождать рисунок , нули не показаны.)
Объединение графов G
1
и G
2
, обозначаемое как G
1
∪ G
2
, представляет
такой граф G
3
=(X
1
∪ X
2
, A
1
∪A
2
), что множество его вершин является
объединением Х
1
и Х
2
, а множество ребер - объединением А
1
и А
2
. Граф G
3
,
полученный операцией объединения графов G
1
и G
2
, показан на рис. 6,д, а его
матрица смежности - на рис. 6,е.
Пересечение графов G
1
и G
2
, обозначаемое как G
1
∩G
2
, представляет
собой граф G
4
=(X
1
∩X
2
, A
1
∩A
2
). Таким образом, множество вершин графа G
4
состоит из вершин, присутствующих одновременно в G
1
и G
2
. Операция
пересечения графов G
1
∩ G
2
показана на рис. 7,а.
Кольцевая сумма двух графов G
1
и G
2
, обозначаемая как G
1
⊕G
2
,
представляет собой граф G
5
, порожденный на множестве ребер А
1
⊕А
2
. Другими
словами, граф G
5
не имеет изолированных вершин и состоит только из ребер,
присутствующих либо в G
1
, либо в G
2
, но не в обоих одновременно.
Кольцевая сумма графов G
1
и G
2
показана на рис.7 ,б.
x
1
x
2
x
3
x
4
x
5
x
6
                                        X4   0   0     0        0        0   0        -1   -1    1        0
                                        X5   0   0     0        0        0   0        0     0    -1       -1
                                        X6   0   0     0        0        0   1        0    0     0        1

Матрица смежности
                                                                    x1                      x2
     X1   X2 X3      X4 X5      X6
X1
X2                                                                                                        x3
X3
X4                                                         x6
X5
X6
                                                                                 x5               x4


.                                                                                                     .

                                  1.3        Операции над графами
        Рассмотрим семь операций над графами, три из которых являются
бинарными, включающими два графа, а остальные четыре - унарные, то есть
определены на одном графе.
        Исходные графы G1 и G2 показаны на рис. 6, а,б. G1=(X1, A1), где X1={xi},
i=1,2,...,6, A={ ai }, i=1,2,...,7. и G2=(X2, A2), где X2={ xi }, i=1,2,...,6, A={a1, a3, a5, a6, a9,
a10}. Матрицы смежности графов показаны на рис.6,в и 6,г соответственно.
(Чтобы не загромождать рисунок , нули не показаны.)
        Объединение графов G1 и G2, обозначаемое как G1 ∪ G2, представляет
такой граф G3=(X1 ∪ X2, A1 ∪A2), что множество его вершин является
объединением Х1 и Х2, а множество ребер - объединением А1 и А2. Граф G3,
полученный операцией объединения графов G1 и G2, показан на рис. 6,д, а его
матрица смежности - на рис. 6,е.
        Пересечение графов G1 и G2, обозначаемое как G1 ∩G2, представляет
собой граф G4=(X1 ∩X2, A1 ∩A2). Таким образом, множество вершин графа G4
состоит из вершин, присутствующих одновременно в G1 и G2. Операция
пересечения графов G1 ∩ G2 показана на рис. 7,а.
         Кольцевая сумма двух графов G1 и G2, обозначаемая как G1 ⊕G2,
представляет собой граф G5, порожденный на множестве ребер А1 ⊕А2. Другими
словами, граф G5 не имеет изолированных вершин и состоит только из ребер,
присутствующих либо в G1, либо в G2, но не в обоих одновременно.
        Кольцевая сумма графов G1 и G2 показана на рис.7 ,б.

Страницы