Составители:
Рубрика:
Пересечением графов G
1
= (V
1
, E
1
) и G
2
= (V
2
, E
2
) называется
граф
G
4
= (V
1
∩ V
2
, E
1
∩ E
2
).
Легко видеть, что операции объединения и пересечения графов
ассоциативны и коммутативны.
В графе G = (V, E) выберем две вершины u, v ∈ V и построим
новый граф G
0
= (V
0
, E
0
), где множество V
0
получается из V отож-
дествлением вершин u и v. Результат отождествления — новую вер-
шину, обозначим w (w — символ, не встречавшийся в обозначении
вершин графа G),
V
0
= V \ {u, v} ∪ w,
а E
0
получается из E заменой всех ребер вида (u, v
1
) на ребра
(w, v
1
), а затем всех ребер вида (u
1
, v) на ребра (u
1
, w) — для неори-
ентированного графа; для ориентированного графа, кроме этого,
требуется заменить все ребра вида (v
1
, u) на ребра (v
1
, w), а также
все ребра вида (v, u
1
) на ребра (w, u
1
).
Определение 5.4. Говорят, что граф G
0
получен из графа G
кратным элементарным гомоморфизмом.
Определение 5.5. По введенному в предыдущем определе-
нии графу G
0
построим граф G
00
исключением из G
0
всех кратных
ребер и петель. Говорят, что граф G
00
получен из G простым эле-
ментарным гомоморфизмом.
Определение 5.6. Последовательное выполнение операций
(простого) элементарного гомоморфизма называется операцией
(простого) гомоморфизма.
Говорят, что граф H гомоморфен (просто гомоморфен) графу
G, если он изоморфен графу, полученному из G операцией (про-
стого) гомоморфизма. Вершина графа H, соответствующая отож-
дествляемым вершинам графа G, называется их образом, а отож-
дествляемые вершины (графа G) — прообразом при рассматривае-
мом гомоморфизме. Сам граф H называется гомоморфным образом
графа G.
Определение 5.7. Гомоморфизм называется независимым,
если никакие две из отождествляемых вершин не соединены реб-
ром.
Определение 5.8. Гомоморфизм называется связным, если
подграф, образованный отождествляемыми вершинами, связен.
48
Страницы
- « первая
- ‹ предыдущая
- …
- 45
- 46
- 47
- 48
- 49
- …
- следующая ›
- последняя »
