ВУЗ:
Составители:
Рубрика:
μ
1
=(e
1
, e
2
, e
3
, e
4
, e
2
)=(v
1
, v
2
, v
3
, v
5
, v
2
, v
3
);
μ
2
=(e
1
, e
4
, e
5
, e
6
, e
2
)=(v
1
, v
2
, v
5
, v
4
, v
2
, v
3
);
μ
3
=(e
1
, e
2
)=(v
1
, v
2
, v
3
).
Маршруты μ
1
и μ
2
, соединяющие вершины v
1
и v
3
, включают одинаковое число
дуг (вершин), но различаются их составом. От маршрута μ
3
их отличает число входящих
в них дуг (вершин), называемое длиной маршрута l.
Если пара вершин (v
i
, v
j
) является элементом бинарного отношения R
2
, то
последовательность вершин (v
1
, ..., v
j
, ..., v
l+1
), представляющая собой маршрут μ длины l,
можно считать элементом l+1-арного отношения R
l+1
.
В графе G=(V, E, C) со взвешенными дугами (ребрами) маршруту μ
сопоставляется вес:
∑
=
=
l
i
i
cc
1
)(
μ
, где c
i
– вес дуги e
i
.
Как следует из примера, маршруты различаются как длиной (μ
1
, μ
3
), так и
перечнем входящих в них дуг (μ
1
, μ
2
).
Цепью называется маршрут, в котором все дуги различны (μ
2
).
Простой называется цепь, в которой все вершины различны (μ
3
).
Циклическим называется маршрут с v
1
=v
l+1
. Он может содержать
повторяющиеся дуги (вершины).
Циклом называется замкнутая цепь.
Простым называется цикл, у которого все вершины различны.
Участком маршрута (e
1
, ..., e
l
) называется его часть: (e
i
, ..., e
j
)
⊂
(e
1
, ..., e
i
, ..., e
j
, ...,
e
l
).
2.8. Деревья
Деревья являются простейшим классом графов. Для них выполняются многие
свойства, которые не всегда выполняются для графов в общем случае. Деревья являются
самым распространенным классом графов, применяемых в программировании. Граф без
циклов называется ациклическим, или лесом. Связанный ациклический граф
называется (свободным) деревом.
Ориентированным деревом (или ордеревом, или корневым деревом)
называется орграф со следующими свойствами:
1. существует единственный узел, полуступень которого равна 0. Он
v
4
e
5
v
5
e
6
e
4
e
3
v
1
e
1
v
2
e
2
v
3
Рис. 25
