Тема 7. Маршруты. Расстояние между вершинами графа. Диаметр и центр графа



Пусть G – конечный н-граф.

Маршрутом в G называется последовательность ребер, в которой каждые два соседних ребра имеют общую вершину:

.

Число ребер в маршруте называется его длиной.

Маршрут М называется маршрутом общего вида, если вершины и ребра повторяются, цепью – если его ребра не повторяются, простой цепью – если его вершины не повторяются,

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

Циклический маршрут М называется маршрутом общего вида, если вершины и ребра повторяются, циклом – если его ребра не повторяются, простым циклом – если его вершины не повторяются (кроме начала и конца).

Граф, не содержащий циклов, называется ациклическим.

Вершины  и  называются связными, если существует маршрут с началом в  и концом в .

Утверждение: Отношение связности вершин графа является отношением эквивалентности и определяет разбиение множества вершин графа на непересекающиеся подмножества .

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

Очевидно, что все подграфы G(Vi) этого графа связны и называются связными компонентами графа.

Расстоянием между вершинами a и b называется длина минимальной простой цепи, связывающей их. Расстояние обозначается d(a, b).

Аксиомы метрики:

1) d(a, b) = d(b, a);

2) d(a, b) ≥ 0, d(a, b) = 0 ↔ a = b;

3) d(a, b) ≤ d(a, c) + d(c, b)

Матрица расстояний, это симметричная квадратная матрица размерности , строки и столбцы которой соответствуют вершинам графа, а на пересечении строк и столбцов записано расстояние между вершинами .

 

В последнем столбце матрицы указан эксцентриситет для каждой вершины: расстояние от данной вершины до наиболее удаленной вершины.

.                                (7.1)

Диаметр графа G – максимальное расстояние между вершинами графа. Диаметр находится по формуле:

.

Используя найденные эксцентриситеты вершин, диаметр можно найти по формуле:

.                                  (7.2)

Радиус графа G – минимальное значение эксцентриситета. Радиус находится по формуле:

.                                   (7.3)

Центрграфа G – такая вершина, для которой .

Замечание.  Центр в графе может быть не единственный.

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

Радиальная цепь графа G – простая цепь, длина которой равна радиусу, соединяющая центр и наиболее удаленную от него вершину графа.

Пример 7.1.

Для н-графа, приведенного на рисунке 7.1, записать 1) маршрут общего вида, 2) не простую цепь, 3) простую цепь, 4) циклический маршрут общего вида,5) не простой цикл, 6) простой цикл.

Решение:

1) Маршрут общего вида – это маршрут, в котором начальная и конечная вершина различны, и некоторые ребра повторяются. М1 = (1, 4, 5, 1, 4, 7, 3). Здесь повторяется ребро (1, 4).

2) Не простая цепь – это маршрут, в котором не повторяются ребра, но повторяются вершины. М2 = (4, 3, 1, 5, 6, 7, 4, 1). Здесь повторяется вершина 1.

3) Простая цепь – это маршрут, в котором не повторяются вершины. М3 = (4, 3, 7, 5, 6).

4) Циклический маршрут общего вида – это маршрут, в котором начальная и конечная вершины совпадают, и некоторые ребра повторяются. М4 = (1, 5, 1, 5, 1). Здесь повторяется ребро (1, 5).

Рисунок 7.1. Построение маршрутов

в неориентированном графе

5) Непростой цикл – это циклический маршрут, в котором не повторяются ребра, но повторяются вершины. М5 = (3, 4, 5, 7, 4, 1, 3). Здесь повторяется вершина 4.

Заметим, что непростой цикл бывает только в графах, в которых существует конфигурация типа «песочные часы».

6) Простой цикл – это циклический маршрут, в котором не повторяются вершины. М6 = (5, 4, 3, 2, 1, 5).

Пример 7.2.

Для н-графа, приведенного на рисунке 7.1, построить матрицу расстояний. Определить диаметр и радиус графа. Указать центры графа. Записать диаметральные и радиальные цепи

Решение:

Для построения матрицы расстояний, сопоставим строки и столбцы вершинам. На пересечении строк и столбцов укажем расстояние между соответствующими вершинами.

d(a, b) 1 2 3 4 5 6 7
1 0 1 1 1 1 2 2 2
2 1 0 1 2 2 3 2 3
3 1 1 0 1 2 2 1 2
4 1 2 1 0 1 2 1 2
5 1 2 2 1 0 1 1 2
6 2 3 2 2 1 0 1 3
7 2 2 1 1 1 1 0 2

На месте (1, 1) стоит 0, так как кратчайший маршрут между вершиной 1 и вершиной 1 – это вырожденный маршрут (без ребер) длины 0.

На месте (1, 2) стоит 1, так как кратчайший маршрут между вершиной 1 и вершиной 2 – это единственное ребро, связывающее эти вершины.

На месте (1, 6) стоит 2, так как кратчайшая простая цепь, между вершиной 1 и вершиной 6 – это цепь из двух ребер (1, 5, 6). Значит, расстояние между этими вершинами равно 2.

И так далее.

В последнем столбце таблицы указано расстояние от данной вершины до наиболее удаленной от нее вершины – эксцентриситет. Их значения находим по формуле (7.1).

Максимум значений последнего столбца – диаметр графа. Откуда d(G) = 3.

Минимум значений последнего столбца – радиус графа. Откуда r(G) = 2.

Центрами являются вершины: 1, 3, 4, 5, 7. Их эксцентриситеты равны радиусу графа.

Для построения диаметральных цепей выясним с помощью матрицы расстояний, какие вершины наиболее удалены друг от друга. Так как максимальное расстояние между вершинами – это диаметр графа, значит, найдем вершины, находящиеся на расстоянии, равном диаметру. Это вершины 2 и 6. Следовательно, все диаметральные цепи в графе связывают эти вершины. Таких цепей две:

D1 = (2, 1, 5, 6) и D2 = (2, 3, 7, 6).

Для построения радиальных цепей выясним с помощью матрицы расстояний, какие вершины наиболее удалены от центров.

От центра 1 на расстоянии радиуса, равного 2, находятся вершины 6 и 7. Значит можно провести радиальные цепи:

R1 = (1, 5, 6) и R2 = (1, 4, 7).

От центра 3 на расстоянии радиуса находятся вершины 5 и 6. Значит можно провести радиальные цепи:

R3 = (3, 4, 5) и R4 = (3, 7, 6).

Далее аналогично.

 

 


Дата добавления: 2018-04-15; просмотров: 9247; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!