Элементы теории графов и их технические приложения - 13 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

13
Рис. 17
Композиция. G=G
1
[G
2
] также имеет VG=V
1
xV
2
в качестве множества вершин
и вершина u=(u
1
, u
2
) смежна с v=(v
1
, v
2
) тогда и только тогда, когда u
1
смежна с v
1
или u
1
=v
1
и u
2
смежна с v
2
. На рис. 17 справа показаны две композиции G
1
[G
2
] и
G
2
[G
1
] и графов G
1
и G
2
представленных слева. Очевидно, что G
1
[G
2
] и G
2
[G
1
] не
изоморфны.
Если G
1
и G
2
– это (p
1
, q
1
) и (p
2
, q
2
) – графы соответсвенно, то для каждой из
определенных выше операций можно найти число вершин и число ребер в
получающемся графе (см. табл. ниже).
Бинарные операции над графами
Операция Число вершин Число ребер
Объединение G
1
∪
G
2
р
1
+р
2
q
1
+q
2
Соединение G
1
+G
2
р
1
+р
2
q
1
+q
2
+р
1
хр
2
Произведение G
1
хG
2
р
1
хр
2
q
1
xq
2
+р
2
хq
1
Композиция G
1
[G
2
] р
1
хр
2
p
1
xq
2
+р
2
2
хq
1
Отождествление (слияние) вершин. Пусть u и v – две вершины графа G, граф
Н=G-u-v. К графу Н присоединим новую вершину v
1
, соединив ее ребром с каждой
из вершин, входящих в объединение окружений вершин u и v в графе G. Говорят,
что построенный граф получается из графа G отождествлением вершин u и v.
Стягивание ребра. Эта операция означает отождествление смежных вершин u и
v в графе G. На рис. 18 показаны граф G, и граф полученный из G стягиванием
ребра {1,2}.
Рис. 18
Граф G называется стягиваемым к графу Н, если Н получается из G в
результате некоторой последовательности стягивания ребер. Очевидно, что любой
непустой связанный граф, отличный от К
1
, стягиваем к К
2
. Но уже не любой

Страницы