§ 7. Маршруты, цепи, циклы

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

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

Цепью называется маршрут, в котором все ребра различны. Простой цепью называется цепь, в которой все вершины различны.

Говорят, что цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и v, обозначается . При этом, если существует цепь, соединяющая вершины u и v, то существует и простая цепь, соединяющая эти вершины.

Циклом называется замкнутая цепь. Простым циклом называется замкнутая простая цепь.

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

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

Для графа G, приведенного на рис. 1.14 является маршрутом длиной 5, – цепь, но не простая, – простая цепь, соединяющая вершины 1 и 5, – цикл, – простой цикл. В графе G содержится три геодезические цепи длиной 2: .

Рассмотрим ориентированные графы. Понятие маршрута в орграфе такое же как и для неориентированных графов.

Определение 1.15. Путем или ориентированным маршрутом в орграфе называется последовательность дуг, в которой конечный узел каждой дуги, кроме последней, является начальным узлом следующей.

Путь называется замкнутым, если конечный узел последней дуги совпадает с началом первой.

Путь называется простым или ориентированной цепью, если каждая дуга в нем используется не более одного раза.

Будем обозначать путь (или маршрут), соединяющий вершину х c , – множество узлов, входящих в путь (маршрут).

Контуром называется простой путь, в котором начало и конец совпадают.

Определение 1.16. Длиной пути называется число входящих в него дуг. Для сети длиной пути называется сумма весов, входящих в путь дуг.

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

Для орграфа на рис. 1.7.1 последовательность является маршрутом, – путь длиной 3, соединяющий узлы 1 и 3, – замкнутый путь, – контур.

Рис. 1.28. Орграф.

§ 8. Метрические и топологические характеристики графов

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

Рис. 1.29. Связный граф. Рис. 1.30. Несвязный граф.

Граф, состоящий только из изолированных вершин, называется вполне несвязным (рис. 1.31).

Рис. 1.31. Вполне несвязный граф.

Определение 1.18. Компонентой связности графа называется максимальный по включению вершин и ребер связный подграф. Число компонент связности графа G обозначается k(G).

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

Граф на рис. 1.32 состоит из трех компонент связности, одной из которых является изолированная вершина.

Рис. 1.32. Граф с тремя компонентами связности.

Определение 1.19. Точкой сочленения графа называется вершина, удаление которой увеличивает число компонент связности. Ребро, удаление которого увеличит число компонент связности, называется мостом. Связный граф, не имеющий точек сочленения, называется блоком.

Рис. 1.33. Граф с единственной точкой сочленения – узлом 3.

Рис. 1.34. Граф с единственным мостом – ребром .

Графы на рис. 1.1, 1.4, 1.11 являются блоками.

Определение 1.20. Ярусом D(v,r) вершины v называют множество вершин, находящихся на одинаковом расстоянии r от вершины v.

Диаметром графа называется длина длиннейшей геодезической, обозначают D(G).

Для графа на рис. 1.33 диаметр

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

Определение 1.21. Эксцентриситетом вершины v в связном графе называется расстояние до максимально удаленной от нее вершины.

Радиусом R(G) называется наименьший из эксцентриситетов вершин.

Вершина v называется центральной, если ее эксцентриситет совпадает с радиусом графа. Центром C(G) графа называется множество центральных вершин.

Заметим, что данные характеристики определяются только для связного графа.

Диаметр графа D(G) совпадает с наибольшим из эксцентриситетов вершин.

Для графа, приведенного на рис. 1.33, эксцентриситет вершины 1 равен 2, эксцентриситет вершины 3 равен 1. Радиус , вершина 3 является центральной.