logo
КЛ

§ 3. Маршруты, цепи, циклы и другие характеристики графа

Рассмотрим неориентированный граф G = < V, U > .

Последовательность

в которой чередуются вершины и ребра и при этом для каждого i = 1, 2,…, n – 1 ребро ui имеет вид называется маршрутом, соединяющим вершины vi u vn .

Очевидно, что маршрут можно задать последовательностью ее вершин v1, v2,…, vn или последовательностью ребер u1, u2,…, un-1 .

Число ребер в маршруте называется его длиной (каждое ребро считается столько раз, сколько раз оно встречается в данном маршруте).

Маршрут, в котором все ребра разные, называется цепью.

Маршрут, в котором все вершины разные, называется простой цепью.

Маршрут, в котором первая и последняя вершины совпадают, называется замкнутым.

Замкнутый маршрут, в котором все ребра различные, называется циклом.

Цикл, в котором все вершины, кроме первой и последней, разные, называется простым циклом.

Граф называется связным, если для любых двух различных вершин существует цепь (маршрут, простая цепь), соединяющая их.

Максимальный по включению вершин связный подграф графа называется его компонентой связности.

Граф является несвязным, если число его компонент связности более одной.

Пример. □

Рис. 4.11

На рис. 4.11 показаны два графа G и G1. Граф G является связным графом, т.к. любая пара его вершин связана цепью. Граф G имеет одну компоненту связности. Граф G1 является несвязным графом, т.к. он имеет две компоненты связности, поэтому любые две вершины из разных компонент связности не связаны цепью. ■

Расстоянием между вершинами vi и vj графа называется минимальная длина цепи, соединяющей эти вершины

,

где длины цепей между вершинами vi и vj .

Максимальное расстояние между вершинами графа G называется диаметром графа :

.

Расстояние является метрической характеристикой графа, т.е. удовлетворяет аксиомам метрики :

1. , причем тогда и только тогда, когда vi = = vj ;

2. ;

3. справедливо неравенство треугольника:

.

Пример. На рис. 4.12 показан граф G . Найти расстояние между вершинами v1 и v5 .

Рис. 4.12

□ Из вершины v1 можно попасть в вершину v5 по ребрам u1, u5 , по ребрам u1, u2, u6, по ребрам u1, u2, u3, u4. Значит

.

Согласно определению расстояния

. ■

Пример. Найти диаметр графа G, показанного на рис. 4.13

Рис. 4.13

□ Определяем расстояния между вершинами :

Максимальным расстоянием является расстояние между вершинами v2 и v4. Значит . ■

Деревом называется связный ациклический (т.е. не имеющий циклов) граф.

Остовом называется остовный подграф, являющийся деревом.

Пример. □

Граф G1 является остовным подграфом графа G, т.к. содержит все вершины. Но он не является остовом, т.к. содержит цикл, т.е. не является деревом. Граф G2 является остовным подграфом графа G и является остовом, т.к. является деревом. ■

Если граф состоит из нескольких компонент связности, каждая из

которых является деревом, то такой граф называется лесом.

Теорема Кёнига. Граф является двудольным тогда и только тогда, когда все его циклы имеют четную длину.

Звездный граф К1, п является деревом. Любое дерево является двудольным графом.

Рассмотрим ориентированный граф .

Характеристики и понятия, определенные для неориентированного графа, можно распространить на ориентированный граф G. Только в орграфе вместо цепь принято говорить путь, вместо простой цикл – контур и необходимо учитывать направление дуг.

Полустепенью исхода вершины v орграфа G называется число дуг графа G, исходящих из вершины v.

Полустепенью захода вершины v орграфа G называется число дуг графа G, заходящих в вершину v.

Для орграфа G существуют понятия связности, сильной связности, односторонней связности.

Для определения связности ориентированного графа не надо учитывать ориентацию дуг.

Орграф G называется сильно связным (или сильным), если любая вершина в нем достижима из всякой другой его вершины (т.е. связаны путями).

Орграф G называется односторонне связным (или односторонним), если для любых двух различных его вершин по меньшей мере одна достижима из другой.

Пример. □

Ориентированные графы G1, G2, G3 являются связными. Граф G1 является сильно связным графом. Граф G2 является несильно (слабо) связным графом. Он имеет две компоненты сильной связности : . Граф G3 является односторонне связным, т.к. нет пути из вершины v3 в вершину v1 . ■