Элементы теории графов. Сюсюкалов А.И - 24 стр.

UptoLike

ВУЗ: 

РГРТУ | Рязань

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

Рубрика: 

19
Определение 5.5. Маршрутом
p
eeeL ...,,,
21
в орграфе
называется такая последовательность его дуг, в которой начало
каждой последующей дуги совпадает с концом предыдущей.
Маршрут можно также задавать порядком прохождения его
вершин. Начало первой дуги маршрута называется его началь-
ной вершиной, а конец последней дуги – конечной вершиной.
Определение 5.6. Маршрут, у которого все дуги разные, на-
зывается цепью. Цепь, содержащая каждую свою вершину ровно
один раз, называется путем.
Определение 5.7. Длиной маршрута называется число дуг,
входящих в маршрут.
Определение 5.8. Расстоянием
vud , между вершинами
u
и
v
называется наименьшая длина маршрута, начальной
вершиной которого является вершина
u
, а конечной – вершина
v
.
Определение 5.9. Полустепенью исхода вершины
v
назы-
вается число дуг, выходящих из вершины
v
. Обозначается
vd
. Полустепенью захода
vd
вершины
v
называется
число дуг, входящих в вершину
v
.
Теорема 5.1. Сумма полустепеней захода вершин орграфа
равна сумме их полустепеней исхода и равна числу дуг орграфа.
Д о к а з а т е л ь с т в о. Поскольку каждая дуга выходит из
одной вершины и входит в одну, то теорема верна.
Определение 5.10. Цепь называется циклом, если ее началь-
ная и конечная вершины совпадают. Цикл орграфа, все верши-
ны которого различные, называется контуром.
Определение 5.11. Вершина орграфа
v
называется дости-
жимой из вершины
u
, если существует маршрут, в котором
вершина
u
является начальной, а вершина
v
– конечной.
Определение 5.12. Орграф называется сильносвязным
(сильным), если для любых вершин
u
и
v
вершина
u
дости-
жима из вершины
v
, а вершина
v
достижима из вершины
u
.
Определение 5.13. Орграф называется односторонним, если
для любых вершин по крайней мере одна достижима из другой.

Страницы