ВУЗ:
Составители:
Рубрика:
12
G
v
=G(VG\v). Аналогично можно определить граф, полученный удалением или
добавлением ребра. Обозначим соответствующие графы через G-x и G+х (рис. 15).
Рис. 15
Улам высказал предположение, что набор подграфов G-v
i
несет полную инфор -
мацию о всем графе G.
2. Операции над графами
Естественно стремиться представить структуру рассматриваемого графа с
помощью графов меньшего размера и более простой структуры. Одна такая
операция уже была рассмотрена, это удаление вершины или ребра, а также переход
к подграфу. Можно из имеющихся графов получить «большие» графы с помощью
операции добавления ребра. Рассмотрим другие операции над графами.
Объединение. Граф Н называется объединением (или наложением) графов F
и G, если VH=VF
∪VG и ЕH=ЕF ∪ЕG, т.е. в Н объединяются множества вершин F и
G и множество ребер. Обозначается H=F
∪G. Аналогично определяется
объединение любого конечного множества графов.
Соединение графов, введенное
Зыковым, обозначается F+G, состоит из F
∪G и всех ребер, соединяющих вершины
графов F и G. Операции объединения и соединения графов иллюстрируются на рис.
16.
Рис. 16
Произведение. Произведением двух графов G
1
=(V
1
, E
1
) и G
2
=(V
2
, E
2
)
называется граф G=G
1
xG
2
, для которого VG=V
1
xV
2
– декартово произведение
множеств вершин исходных графов, а EG определяется следующим образом:
вершины (u
1
, u
2
) и (v
1
, v
2
) смежны в графе G тогда и только тогда, когда или u
1
=v
1
, а
u
2
и v
2
смежны в G
2
или u
2
=v
2
, а u
1
и v
1
смежны в G
1
(рис. 17).
Страницы
- « первая
- ‹ предыдущая
- …
- 10
- 11
- 12
- 13
- 14
- …
- следующая ›
- последняя »
