что такое радиус графа

Графы дорожных сетей и алгоритмы работы с ними

В математике сети дорог (автомобильных и не только) представляются взвешенным графом. Населенные пункты (или перекрестки) — это вершины графа, ребра — дороги, веса ребер — расстояния по этим дорогам.

Для взвешенных графов предлагается множество алгоритмов. Например, популярный алгоритм Дейкстры для поиска кратчайшего пути от одной вершины до другой. У всех этих алгоритмов есть общая принципиальная (для математики) особенность — они универсальны, т.е. могут успешно применяться для графов любой конструкции. В частности, для каждого алгоритма известна его сложность – она примерно соответствует увеличению времени выполнения алгоритма в зависимости от числа вершин графа. Все это подробно можно прочитать, например, в википедии.

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

Мы не знаем эти правила, однако, работая с дорожными сетями, вполне можно использовать алгоритмы, которые эффективны для графов дорог, хотя и не подходят для графов в универсальном или математическом смысле. Рассмотрим здесь два таких алгоритма.

Несколько важных понятий и условностей

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

2. Матрица кратчайших расстояний (МКР) – ее маленький и простой пример можно найти во многих дорожных атласах. Эта табличка обычно называется примерно так: «расстояния между наиболее важными городами». Она выглядит как часть матрицы ниже или выше главной диагонали (из верхнего левого в нижний правый угол), потому что с другой стороны главной диагонали точно такие же цифры, другими словами элемент М(i,j)= М(j,i). Это происходит, потому что граф, как говорят математики, неориентированный. Строки и столбцы соответствуют городам (вершинам графа). В реальности такая таблица намного больше, так как в вершины графа, кроме городов, входят все деревни и перекрестки, но напечатать такую большую таблицу в атласе, естественно, невозможно.

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

Наша МКР может быть: а) известна заранее, потому что мы ее подсчитали одним из методов поиска МКР; б) мы можем не знать МКР, а определять ее построчно по мере необходимости. Построчно – это значит, что для требуемой строки рассчитываются расстояния только от соответствующей ей вершины до остальных вершин, например, методом Дейкстры.

3. Еще пара понятий. Эксцентриситет данной вершины – это расстояние от этой вершины до самой удаленной от нее. Радиус графа – это наименьший из эксцентриситетов всех вершин. Центр графа – вершина, эксцентриситет которой равен радиусу.

Как это выглядит на практике. Центр дорожной сети – это город или перекресток, наименее удаленный от всех остальных пунктов этой сети. Радиус – максимальное расстояние от этого центрального узла до самого удаленного.

4. Степень вершины – количество ребер, которое присоединено к вершине.
У графов дорожных сетей, средняя степень всех вершин находится в районе от 2 до 4. Это вполне естественно – сложно и дорого строить перекрестки с большим количеством примыкающих дорог, не менее сложно потом пользоваться такой дорожной сетью. Графы, с невысокой средней степенью вершин называются разреженными, как видим, графы дорожных сетей именно такие.

Задача 1. Поиск радиус и центра графа по матрице кратчайших расстояний

Заметим, что у графа может быть несколько центров, но мы хотим найти любой из них.

Как задача решается в общем случае? Полным просмотром МКР. Ищется максимальный элемент в строке (эксцентриситет каждой вершины), а потом из этих максимальных элементов находится минимальный.

Это далеко не самый быстрый способ. Для чего нужно быстрее, если, казалось бы, радиус и центр графа можно найти один раз? Например, существуют задачи и алгоритмы на них, где в ходе перебора вершины постоянно «переобъединяются» в группы, а критерием для каждой группы является ее радиус. В этом случае радиус пересчитывается многократно, и скорость его поиска становится важным параметром. Как найти радиус быстрее?

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

Посмотрим, за счет чего это получается. Рассмотрим значения в одной строке матрицы МКР, другими словами, рассмотрим расстояния от одной вершины до всех остальных. Несложно доказать, что радиус графа не может быть больше чем максимальное значение в этой строке, и не может быть меньше чем минимальное значение в этой строке. Говоря математически, мы нашли верхнюю и нижнюю границу числа и если они совпадут – мы найдем число.

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

Здорово, но такая ситуация на графах дорожных сетей маловероятна и решать задачу таким образом не получится. Поступим хитрее.
Возьмем пару строк В1 и В2. Из них сформируем вектор М таким образом: М(i)=max[B1(i),B2(i)]. Несложно доказать, что если для всех строк i значение min(M(i)) равно максимальному значению в столбце А, то, опять таки, А – центр, а найденное min(M(i)) – радиус.
Если пары строк окажется недостаточно, можно взять несколько строк, например три: B1, B2 и B3, тогда М(i)=max[B1(i),B2(i),B3(i)]. Особенность графов дорожных сетей состоит в том, что много строк не понадобится (удастся уложиться в десяток). Это легко проверить, поэкспериментировав на существующих графах сетей, скачав их из интернета: ссылка.

В общем случае и с точки зрения математики это, конечно, не так. Вполне можно построить теоретический граф в котором придется использовать очень много строк В (почти все, кроме, А). Вот только невозможно построить реальную дорожную сеть такого вида — денег не хватит.

Осталась последняя задача. Как быстро найти эти удачные строки B1, B2 и т.д. Для графов реальных дорожных сетей это сделать очень просто и быстро. Это будут максимально удаленные друг от друга вершины, но не обязательно самые удаленные (говоря математически, находить диаметр графа нам не требуется). Берем любую вершину, находим для нее самую дальнюю, для новой опять самую дальнюю и так, пока пара вершин не окажется самой дальней друг для друга.

Мы получили пару вершин В1 и В2. Находим для пары вектор М, как описано выше. Строка, в которой мы нашли min(M(i)) — претендент на центр, обозначим его А. Если в столбце А значение min(M(i)) – максимальное, то уже найдены центр и радиус. Если же нет, значит максимальное значение в столбце А соответствует расстоянию до другой вершины (не B1 и не B2). Значит, мы получили новую вершину B3 в список на поиск вектора М. Как вариант, можно и для B3 поискать самую удаленную вершину и если она не В1 и не B2, добавить ее как В4. Таким образом, увеличиваем список вершин B, пока центр и радиус не будут найдены.

Задача 2. Поиск матрицы кратчайших расстояний

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

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

Начнем с простого, с вершины со степенью 1. Ее можно удалить в любом случае. Через нее не проходит никаких кратчайших путей, кроме путей к самой вершине, причем идут они именно через ту вершину, к которой была присоединена удаляемая вершина.

Пусть А – вершина со степенью 2 и присоединена она в вершинам В1 и В2. Если маршрут В1-А-В2 длиннее или равен ребру В1-В2, через точку А не проходит никаких маршрутов, кроме маршрутов к самой точке А (все остальные проходят через В1-В2). Значит, точку А можно удалить. В ином случае, т.е. если В1-А-В2 короче В1-В2 или ребра В1-В2 вообще нет, вершину А можно удалить, установив вес ребра В1-В2 равным сумме весов: |В1-А|+|А-В2|. Маршрут от А до других точек проходит либо через В1, либо через В2, если будут известны расстояния для В1 и В2, расстояния от А так же легко вычислить.

По такому же принципу можно удалить вершину с любой степенью, заменяя, по мере необходимости, Вi-А-Вj на Bi-Bj. Правда, нужно понимать, что чем больше степень вершины, тем больше возможных ребер надо проверить. Для вершины степени n это число равно n(n-1)/2.

Графы дорожных сетей имеют уникальную особенность такого рода: многие вершины могут быть удалены не только без роста, но и с уменьшением степени смежных вершин. Причем, если некоторая вершина не может быть «успешно» удалена сейчас, она может быть «успешно» удалена позже, после удаления некоторых, смежных с ней вершин.

Соответственно, нам просто требуется на каждом шаге правильно выбирать вершины на удаление, начиная с тех, которые удаляются более «удачно».

Сам алгоритм более подробно можно посмотреть здесь. Там описано, как удалить вершину, сохраняя расстояния и пути между оставшимися. Этот процесс называется разборкой. Там описано, как восстановить потом граф обратно, добавляя вершины в обратном порядке по одной, как пересчитывать при этом МКР. Этот процесс называется сборкой.

Там же приведены результаты использования алгоритма на графах дорожных сетей США по ссылке.

Источник

Как найти диаметр графа

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

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

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

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

Для графа 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₁) = 3, r(v₂) = 2, r(v₃) = 2, r(v₄) = 2, r(v₅) = 3. Минимальное из полученных чисел является радиусом графа G, максимальное – диаметром графа G. Значит, R(G) = 2 и D(G) = 3, центрами являются вершины v₂, v₃, v₄.

Срочно?
Закажи у профессионала, через форму заявки
8 (800) 100-77-13 с 7.00 до 22.00

Определение

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

Радиусом графа называется минимальный эксцентриситет среди всех вершин графа

Диаметром графа – это наибольшее расстояние между всеми парами вершин графа

Центральной вершиной графа является вершина чей эксцентриситет равен радиусу графа.

Периферийной вершиной графа является вершина чей эксцентриситет равен диаметру графа.

Поиск радиуса и диаметра

© Граф Online – создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2016. (Edit – History – Print – Recent Changes – Search)

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

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

.

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

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

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

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

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

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

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

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

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

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

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

		…
			…
			…
…	…	…	…	…	…
			…

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

. (7.1)

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

.

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

. (7.2)

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

. (7.3)

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

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

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

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

Пример 7.1.

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

Решение:

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

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

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

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

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

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

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

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

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

Пример 7.2.

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

Решение:

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

d(a, b)	1	2	3	4	5	6	7
1	1	1	1	1	2	2	2
2	1	1	2	2	3	2	3
3	1	1	1	2	2	1	2
4	1	2	1	1	2	1	2
5	1	2	2	1	1	1	2
6	2	3	2	2	1	1	3
7	2	2	1	1	1	1	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. Следовательно, все диаметральные цепи в графе связывают эти вершины. Таких цепей две:

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

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

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

Дата добавления: 2018-04-15 ; просмотров: 1731 ; ЗАКАЗАТЬ РАБОТУ

Источник