ВУЗ:
Составители:
72
Операции над графами. Естественно стремиться представить
структуру данного графа G с помощью графов меньшего размера и
более простой структуры. Это делается с помощью операции над
графами.
1. Объединением G=G
1
∪
G
2
называют граф, множество вершин
и дуг которого определяется как X=Х
1
∪
Х
2
, U=U
1
∪
U
2
.
Эта операция имеет смысл для случаев “пересекающихся” и
“непересекающихся” графов. Например, пусть G
1
=К
2
и G
2
=К
3
, тогда
если К
2
и К
3
не пересекаются, то результат операции приведен на
рис. 2.40, а; если же они пересекаются, то результат операции – на
рис 2.40, б.
2. Операция соединения графов G
1
и G
2
, обозначается как
G
1
+G
2
, она имеет смысл только для непересекающихся графов, и со-
стоит из G
1
∪
G
2
и всех рёбер, соединяющих Х
1
и Х
2
. Результат соеди-
нения двух графов К
2
и К
3
приведен на
рис. 2.41. Число вершин n в результи-
рующем графе определяется из выраже-
ния n=n
1
+n
2
, где n
1
и n
2-
- число вершин
в исходных графах. Число дуг m в иско-
мом графе вычисляется как
m=m
1
+m
2
+n
1
n
2
, где m
1
и m
2
- число дуг в исходных графах.
3. Произведение G
1
×
G
2
, есть граф G , в котором X=Х
×
Х2 , и две
вершины u=(u
1
,u
2
) и v
1
=(v
1
,v
2
) в G смежны, если [u
1
=v
1
и u
2
смежна с
Рис. 2.40
a
=
b
а
c
d
e
∪
b
а
c
d
e
б
∪
b
а
c
a
d
=
c
d
b
а
Рис. 2.41.
=
+
b
а
c
d
e
b
а
c
d
e
Страницы
- « первая
- ‹ предыдущая
- …
- 74
- 75
- 76
- 77
- 78
- …
- следующая ›
- последняя »
