Составители:
Рубрика:
Вторая параллельная форма (см. рис. 7)
Данные 0: a
1
, a
2
, a
3
, a
4
, a
5
, a
6
, a
7
, a
8
.
Ярус 1. a
1
a
2
, a
3
a
4
.
Ярус 2. a
5
a
6
, a
7
a
8
.
Ярус 3. a
1
a
2
+ a
3
a
4
, a
5
a
6
+ a
7
a
8
.
Ярус 4. (a
1
a
2
+ a
3
a
4
)(a
5
a
6
+ a
7
a
8
).
Третья параллельная форма (см. рис. 8)
Данные 0: a
1
, a
2
, a
3
, a
4
, a
5
, a
6
, a
7
, a
8
.
Ярус 1. a
1
a
2
, a
3
a
4
.
Ярус 2. a
1
a
2
+ a
3
a
4
, a
5
a
6
.
Ярус 3. a
7
a
8
.
Ярус 4. a
5
a
6
+ a
7
a
8
.
Ярус 5. (a
1
a
2
+ a
3
a
4
)(a
5
a
6
+ a
7
a
8
).
Нетрудно видеть, что все три графа отличаются друг от друга
лишь топологической сортировкой, что и должно быть при изобра-
жении одного и того же алгоритма.
§ 5. Изоморфизм графов. Операции гомоморфизма
Определение 5.1. Два графа (соответственно, ориенти-
рованных графа) называются изоморфными, если между множе-
ствами вершин и ребер (вершин и дуг) можно установить вза-
имно однозначное соответствие, сохраняющее отношение инци-
денции (соответственно, отношение инциденции и ориентацию).
Изоморфизм графов представляет собой эквивалентность (т.е.
отношение со свойствами рефлексиности, симметричности и тран-
зитивности).
Определение 5.2. Подграфом графа G называется граф, у
которого все вершины и все ребра принадлежат G (для них сохра-
няются прежние отношения инциденции). Подграф, у которого
вершины те же, что и у G, называется остовным подграфом для
G.
Определение 5.3. Объединением графов G
1
= (V
1
, E
1
) и G
2
=
(V
2
, E
2
) называется граф
G
3
= (V
1
∪ V
2
, E
1
∪ E
2
).
47
Страницы
- « первая
- ‹ предыдущая
- …
- 44
- 45
- 46
- 47
- 48
- …
- следующая ›
- последняя »
