Элементы теории графов и их технические приложения - 15 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

15
v
L+1
его вершин (наличие ребер подразумевается), а также последовательностью е
1
,
е
2
,…, е
L
ребер.
Маршрут называется
цепью, если все его ребра различны, и простой цепью,
если все его вершины (а, следовательно, и ребра), кроме, возможно, крайних,
различны. Маршрут называется
циклическим, если v
1
=v
L+1
(замкнутый маршрут).
Циклическая цепь называется
циклом, а циклическая, простая цепь – простым
циклом (все его n вершин различны). Число n ребер в маршруте (v
1
, v
n+1
) называется
его
длиной. Простой цикл длины n называется n-циклом, 3-цикл часто называется
треугольником. Длина всякого простого цикла не менее трех, поскольку в таком
графе нет петель и кратных ребер. Минимальная из длин циклов графа называется
его
обхватом, обозначается g(G). Окружение графа G (обозначается с(G)) – длина
самого длинного простого цикла графа G. Эти понятия не определены, если в G нет
циклов.
Очевидно, что любую цепь графа можно рассматривать как его подграф.
Рассмотрим некоторую цепь Р вида v
1
, v
2
,…, v
L+1
графе G, v
i
и v
j
– входящие в
нее вершины (i<j). Очевидно, что часть v
i
, v
i+1
,…, v
j
цепи Р, начинающаяся в
вершине v
i
и заканчивающаяся в v
j
сама является цепью графа G и называется (v
i
, v
j
)
–
подцепью цепи Р.
Рис. 21
Для графа G, изображенного на рис. 21маршруты (1,2) и (1,2,4,7) являются
простыми цепями; (1,2,4,7,8,4) – цепь не являющаяся простой; (1,2,4,7,8,4,2) –
маршрут не являющийся цепью; (1,2,4,1) – простой цикл. Обхват этого графа
g(G)=3. Для ориентированного графа вводится, аналогичным образом, понятие
ориентированного маршрута. Аналогом цепи в этом случае служит путь
(ориентированная цепь). Вершина v называется достижимой из вершин u, если
существует (u, v) – путь
. Контур – это конечный путь, у которого начальная и
конечная вершины совпадают. При этом контур называется
элементарным, если
все его вершины различны (за исключением начальной и конечной, которые
совпадают). Контур единичной длины, образованный дугой вида (а, а), называется
петлей. Петля связывает точку саму с собой.
Замечание
. Понятия ребра, цепи и цикла отличаются от понятия дуги, пути и
контура только тем, что для последних принимается во внимание ориентация
(направление).
С понятием неориентированного графа связана важная характеристика,
называемая
связностью графа. Граф называется связным, если любые две его
несовпадающие вершины соединены маршрутом (цепью или простой цепью).
В силу того, что при u
≠ v произвольный (u, v) – маршрут, не являющийся
простой цепью, после устранения «лишних кусков», превращается в простую (u, v)-
цепь, то верны следующие утверждения.

Страницы