Графы дорожных сетей и алгоритмы работы с ними. Математическая модель

Утверждение. Если для двух вершин существует маршрут, связывающий их, то обязательно найдется минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута через d(v, w).

Определение. Величину d(v, w) (конечную или бесконечную) будем называть расстоянием между вершинами v, w . Это расстояние удовлетворяет аксиомам метрики:

1) d(v, w) 0, причем d(v, w) = 0 тогда и только тогда, когда v= w;

2) d(v, w) = d(w, v);

3) d(v, w) d(v, u) + d(u, w).

Определение. Диаметром связного графа называется максимально возможное расстояние между двумя его вершинами.

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

Пример 82.

Для графа G, изображенного на рис. 3.16, найти радиус, диаметр и центры.

Рис. 3.16. Граф для примера 82

Решение.

Чтобы определить центры, радиус, диаметр графа G , найдем матрицу D(G) расстояний между вершинами графа, элементами d ij которой будут расстояния между вершинами v i и v j . Для этого воспользуемся графическим представлением графа. Заметим, что матрица D(G) симметрична относительно главной диагонали.

С помощью полученной матрицы для каждой вершины графа G определим наибольшее удаление из выражения: для i, j = 1, 2, …, 5 . В результате получаем: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3. Минимальное из полученных чисел является радиусом графа G , максимальное – диаметром графа G . Значит, R(G) = 2 и D(G) = 3 , центрами являются вершины v 2 , v 3 , v 4 .

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

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

Радиус графа – минимальный эксцентриситет вершин, а диаметр графа – максимальный эксцентриситет вершин.

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

Периферийные вершины имеют эксцентриситет, равный диаметру.

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

Теорема 12.1. В связном графе диаметр не больше ранга его матрицы смежности.

Теорема 12.2. (Жордана) Каждое дерево имеет центр, состоящий из одной или двух смежных вершин.

Теорема 12.3. Если диаметр дерева четный, то дерево имеет единственный центр, и все диаметральные цепи проходят через него, если диаметр нечетный, то центров два и все диаметральные цепи содержат ребро, их соединяющее.

Очевидно практическое значение центра графа. Если, например, речь идет о графе дорог с вершинами-городами, то в математическом центре целесообразно размещать административный центр, складские помещения и т.п. Этот же подход можно применять и для взвешенного графа, где расстояния – это веса ребер. В качестве веса можно брать евклидовое расстояние, время или стоимость передвижения между пунктами.

Пример 12.5. Найти радиус, диаметр и центр графа, изображенного на рис. 12.1.

Решение. В данной задаче удобно использовать матрицу расстояний S . Элемент этой квадратной симметричной матрицы равен расстоянию между вершиной i и вершиной j . Для графа, показанного на рис. 12.1, матрица расстояний имеет следующий вид:

Вычислим эксцентриситет каждой вершины. Эту величину можно определить как максимальный элемент соответствующего столбца матрицы расстояний (или строки – поскольку матрица S симметрична). Получаем

Радиус графа r – минимальный эксцентриситет вершин. В данном случае r = 2. Такой эксцентриситет имеют вершины № 2, № 4 и № 5. Эти вершины образуют центр графа. Диаметр графа d – максимальный эксцентриситет вершин. В данном случае d = 3. Такой эксцентриситет имеют вершины № 1 и № 3, это периферия графа. В исследованном графе вершины оказались либо центральными, либо периферийными. В графах большего порядка существуют и другие вершины.

Эксцентриситеты вершин небольшого графа легко вычислять непосредственным подсчетом по рисунку. Однако не всегда граф задан своим рисунком. Кроме того, граф может иметь большой размер. Поэтому необходим другой способ решения предыдущей задачи. Известна следующая теорема.

Теорема 12.4. Пусть – матрица смежности графа G без петель и , где . Тогда равно числу маршрутов длины k от вершины к вершине .

Решение задач теории графов с помощью различных преобразований матрицы смежности называют алгебраическим методом .

Пример 12.6. Найти матрицу расстояний графа, изображенного на рис. 12.1, алгебраическим методом.

Решение. Матрица смежности данного графа равна:

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

Диагональные элементы матрицы расстояний – нули. Умножаем матрицу смежности на себя:

Согласно теореме между вершинами 2 и 3, 1 и 4 и т.д. имеется некоторое число маршрутов длиной 2 (поскольку степень матрицы равна двум). Число маршрутов здесь не используется, важен сам факт наличия маршрута и его длина, на что и указывает ненулевой элемент степени матрицы, не совпадающий с элементом, отмеченным при вычислении маршрута меньшей длины. Проставляем 2 в незаполненные элементы матрицы расстояний и получаем следующее приближение:

Осталось неизвестным расстояние между вершинами 1 и 3. Будем умножать матрицу смежности саму на себя до тех пор, пока в матрице не появится ненулевой элемент . Тогда соответствующий элемент матрицы расстояний равен степени матрицы смежности: . На следующем шаге получаем

следовательно, , и окончательно

Полученная матрица совпадает с матрицей расстояний S (12.2), найденной непосредственными вычислениями по рисунку.

Пусть G(V,X) – псевдограф и пусть вершины v и w (v¹w) данного графа можно соединить маршрутом. Тогда обязательно существует и минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута d(v, w). Положим также d(v, v) =0 для любой вершины vÎV; d(v, w) = ¥, если не существует маршрута, соединяющего v и w.

Определенная таким образом величина d(v,w) для любых вершин v и w графа G(V, X) называется расстоянием между v и w.

Число расстояний в графе с n вершинами равно числу сочетаний C n 2 .

Пусть граф G(V,X) связный. Определим для него следующие понятия:

Диаметр графа : d(G) = maxd(v, w).

Эксцентриситет (максимальное удаление) вершины : r(v) = maxd(v, w);

Радиус графа: r(G) = min r(v);

Центр графа : любая вершина vÎV,такая, что r(v) = r(G).

Диаметр графа, эксцентриситеты вершин, радиус графа и центры графа называются метрическими характеристиками графа.

Пример. Найти метрические характеристики графа, заданного диаграммой:

Найдем все расстояния, учитывая, что d(v, w) = d(w, v).

Число расстояний в данном графе С 5 2 = 5!/3!2! = 10: d(v 1 , v 2) =1, d(v 1 , v 3) = 2, d(v 1 , v 4) = 2, d(v 1 , v 5) = 3, d(v 2 , v 3) = 1, d(v 2 , v 4) = 1, d(v 2 , v 5) = 2, d(v 3 , v 4) = 1, d(v 3 , v 5) = 2, d(v 4 , v 5) = 1.

Диаметр графа d(G) =3.

Эксцентриситеты вершин: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3.

Радиус графа r(G) = 2.

Центры графа v 2 , v 3 , v 4 .

3. Минимальные маршруты в нагруженных графах

Граф G(V, X) называется нагруженным, если на множестве ребер графа задана функция, называемая весовой, которая ставит в соответствие каждому ребру х ÎХ графа некоторое число l(x). Значение l(x) называется длиной дуги.

Величине l(x) можно придать разный смысл: затраты на транспортировку, время проезда, расстояние между пунктами, расход бензина и т.д.

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

Заметим, что если для всех х Î Х l(x) = 1, то граф можно рассматривать как ненагруженный.

Маршрут в графе G(V, X) из вершины v в вершину w (v¹w), называется минимальным, если он имеет минимальную длину среди всех маршрутов в графе G(V, X) из вершины v в вершину w.

Ограничимся графами, для которых l(x)>0.

При поиске минимального маршрута в нагруженном графе с l(x)>0

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

любой минимальный маршрут является простой цепью.

Рассмотрим теперь задачу поиска минимального маршрута в нагруженном графе.

Пусть граф G(V,X) нагруженный, число вершин n ³ 2, необходимо построить минимальный маршрут из v 1 в v n .

Приведем алгоритм.

Шаг 1. Каждой вершине присвоить индекс a(v i): a(v 1) = 0, a(v i) = ¥, i ¹ 1. окрасить вершину v 1 и положить v = v 1 .

Шаг 2. Для каждой неокрашенной вершины v j изменить индекс по правилу:

a(v j) = min {a(v j), a(v) + l(v, v j)}.

Окрасить ту из вершин, для которой a(v j) окажется наименьшим.. окрасить также ребро, ведущее в выбранную на данном шаге вершину v j . Положить v = v j .

Шаг 3. Если v = v j , закончить процедуру, так как кратчайший маршрут из v 1 в v n . если v ¹ v n , то перейти к шагу 2.

Замечание. Шаг 2 невозможен, если все a(v j)= ¥. В этом случае вершина v n недостижима.

Применим изложенный алгоритм к заданному диаграммой графу. Найдем в нем кратчайший маршрут из v 1 в v 6 .

Шаг 1. Окрасим вершину v 1 . Присвоим вершинам индексы: a(v 1) =0, a(v 2) = a(v 3)=…= a(v n)=¥. Полагаем v 1 = v.

a(v 2) = min {¥, 0+4} = 4,

a(v 3) = min {¥, 0+7} = 7,

a(v 4) = min {¥, 0+3} = 3,

a(v 5) = min {¥, 0+¥} = ¥,

a(v 6) = min {¥, 0+¥} = ¥.

Окрашиваем вершину v 4 и ребро {v 1 , v 4 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 4 .

a(v 2) = min {4, 3+¥} = 4,

a(v 3) = min {7, 3+¥} = 7,

a(v 5) = min {¥, 3+3} = 6,

a(v 6) = min {¥, 3+¥} = ¥.

Окрашиваем вершину v 2 и ребро {v 1 , v 2 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 2 .

a(v 3) = min {7, 4+3} = 7,

a(v 5) = min {6, 4+2} = 6,

a(v 6) = min {¥, 4+¥} = ¥.

Окрашиваем вершину v 5 и ребро {v 4 , v 5 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 5 .

a(v 3) = min {7, 6+¥} = 7,

a(v 6) = min {¥, 6+2} = 8.

Окрашиваем вершину v 3 и ребро {v 1 , v 3 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 3 .

a(v 6) = min {8, 7+2} = 8.

Окрашиваем вершину v 6 и ребро {v 5 , v 6 }.

Так как вершина v 6 окрашена, то работу прекращаем. Получили минимальный маршрут v 1 v 4 v 5 v 6 , длина которого равна 8 .

Заметим, что это в данном случае не единственный для вершин v 1 и v 6 минимальный маршрут, т.к. в алгоритме имелась возможность окрасить вместо ребра {v 4 , v 5 } ребро {v 2 , v 5 }, тогда бы получили другой маршрут той же длины.

4. Задачи на деревьях

Ациклическим называется граф, в котором отсутствуют циклы.

Граф без циклов называется лесом.

Дерево – это связный ациклический граф.