Основные понятия теории графов. Гладких О.Б - 21 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

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

Рубрика: 

156
Рис. 6.3.
Описанный алгоритм относится к категории «жад-
ных»: на каждом шаге мы выбираем самое деше-
вое продолжение пути.
21
4B1.4. Маршруты, циклы в неориентированном
графе
Пусть G – неориентированный граф.
Определение 1.20. Маршрутом или цепью в G на-
зывается такая последовательность (конечная или
бесконечная) ребер a
1
, a
2
,... a
n
..., что каждые со-
седние два ребра a
i
и a
i+1
имеют общую инцидент-
ную вершину.
Одно и то же ребро может встречаться в
маршруте несколько раз. В конечном маршруте
(a
1
,a
2
,...a
n
) имеется первое ребро a
1
и последнее
ребро a
n
. Вершина x
1
, инцидентная ребру a
1
, но не
инцидентная ребру a
2
, называется началом мар-
шрута, а вершина x
n
, инцидентная ребру a
n
, но не
инцидентная ребру a
n–1
, называется концом мар-
шрута.
Определение 1.21. Длиной (или мощностью)
маршрута называется число ребер, входящих в
маршрут, причем каждое ребро считается столько
раз, сколько оно входит в данный маршрут.
Замкнутый маршрут называется циклом.
Пример 1.11.
В изображенном на рис. 8 графе рассмотрим
два маршрута из вершины x
1
в вершину x
4
:
M
1
= (a
1
, a
2
, a
4
) и M
2
= (a
1
, a
2
, a
5
, a
6
). 
                                                   1.4. Маршруты, циклы в неориентированном
                                                  4B




                                                                         графе
                                                        Пусть G – неориентированный граф.
                                                 Определение 1.20. Маршрутом или цепью в G на-
                                                 зывается такая последовательность (конечная или
                                                 бесконечная) ребер a1, a2,... an..., что каждые со-
                                                 седние два ребра ai и ai+1 имеют общую инцидент-
                                                 ную вершину.
                                                        Одно и то же ребро может встречаться в
                   Рис. 6.3.                     маршруте несколько раз. В конечном маршруте
Описанный алгоритм относится к категории «жад-   (a1,a2,...an) имеется первое ребро a1 и последнее
ных»: на каждом шаге мы выбираем самое деше-     ребро an. Вершина x1, инцидентная ребру a1, но не
вое продолжение пути.                            инцидентная ребру a2, называется началом мар-
                                                 шрута, а вершина xn, инцидентная ребру an, но не
                                                 инцидентная ребру an–1, называется концом мар-
                                                 шрута.
                                                 Определение 1.21. Длиной (или мощностью)
                                                 маршрута называется число ребер, входящих в
                                                 маршрут, причем каждое ребро считается столько
                                                 раз, сколько оно входит в данный маршрут.
                                                        Замкнутый маршрут называется циклом.
                                                                     Пример 1.11.
                                                       В изображенном на рис. 8 графе рассмотрим
                                                 два маршрута из вершины x1 в вершину x4:
                                                        M1 = (a1, a2, a4) и M2 = (a1, a2, a5, a6).




                         156                                                21

Страницы