Анализ графов на ЭВМ - 24 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

крайних, различны. Маршрут (v
i
, v
i+1
) называется циклическим, если v
i
=
v
i+1
. Циклическая цепь называется циклом, циклическая простая цепь —
простым циклом. Число ребер в маршруте (v
i
, v
i+1
) определяет его длину.
Простой цикл единичной длины называется единичным циклом. Длина
всякого цикла в простом графе (без петель кратных ребер) и кратных
ребер) минимум равна трем. Минимальная из длин циклов графа
называется его обхватом.
Любая цепь графа может рассматриваться как его подграф. В цепи Q
графа G, заданной последовательностью вершин v
1
, v
2
,…,v
n
, можно
выделить две вершины v
i
, v
j
. Часть цепи Q, начинающаяся в v
i
и
заканчивающаяся в v
j
(v
i
, v
i+1
,…,v
j-1
, v
j
), сама является цепью графа G. Цепь
(v
i
, v
j
) называется полуцепью цепи Q. На рис. 9 приведен граф G, в котором
(1,2) и (1, 2, 3, 5) - простые цепи. Цепь (1, 3, 5, 4, 3, 2) не является простой
цепью. Маршрут (1, 2, 3, 5, 4, 3, 2) — не цепь. Цепь (1, 2, 3, 1) — простой
цикл. Обхват рассматриваемого графа равен трем.
Рис. 9. Граф с обхватом, равным трем
В ориентированных графах маршрут ориентированный и является
последовательностью вида (1). Аналогом цепи с в ориентированном графе
служит путь (ориентированная цепь). Вершина v
j
в ориентированном графе
называется достижимой из вершины v
i
, если существует путь (v
i
, v
j
).
v
1
v
2
v
3
v
4
v
5
24
крайних, различны. Маршрут (vi, vi+1) называется циклическим, если vi =
vi+1. Циклическая цепь называется циклом, циклическая простая цепь —
простым циклом. Число ребер в маршруте (vi, vi+1) определяет его длину.
Простой цикл единичной длины называется единичным циклом. Длина
всякого цикла в простом графе (без петель кратных ребер) и кратных
ребер) минимум равна трем. Минимальная из длин циклов графа
называется его обхватом.
      Любая цепь графа может рассматриваться как его подграф. В цепи Q
графа G, заданной последовательностью вершин v1, v2,…,vn, можно
выделить две вершины vi, vj. Часть цепи Q, начинающаяся в vi и
заканчивающаяся в vj(vi, vi+1,…,vj-1, vj), сама является цепью графа G. Цепь
(vi, vj) называется полуцепью цепи Q. На рис. 9 приведен граф G, в котором
(1,2) и (1, 2, 3, 5) - простые цепи. Цепь (1, 3, 5, 4, 3, 2) не является простой
цепью. Маршрут (1, 2, 3, 5, 4, 3, 2) — не цепь. Цепь (1, 2, 3, 1) — простой
цикл. Обхват рассматриваемого графа равен трем.


                                             v2



                              v1                       v3



                                   v5             v4



                      Рис. 9. Граф с обхватом, равным трем
       В ориентированных графах маршрут ориентированный и является
последовательностью вида (1). Аналогом цепи с в ориентированном графе
служит путь (ориентированная цепь). Вершина vj в ориентированном графе
называется достижимой из вершины vi, если существует путь (vi, vj).




                                        24

Страницы