Использование особенностей взвешенных графовдля более быстрого определения их характеристик | ПДМ. 2012. № 2(16).

Использование особенностей взвешенных графовдля более быстрого определения их характеристик

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

Using weighted graphs features for fast searchingtheir parameters.pdf ВведениеВ практических задачах взвешенные графы чаще всего соответствуют некоторойреальной физической сети (например, автомобильных дорог или передачи данных).При проектировании и строительстве таких сетей обязательно учитывается тот факт,что связывание пары узлов ребром имеет некоторую себестоимость, которая зависит отдлины участка. В свою очередь, длина участка некоторым образом задает вес ребра.Таким образом, необходимость снижения себестоимости определяет как топологиюсамой сети, так и вид графа, который её описывает.Другими словами, взвешенный граф, построенный для такой сети, не являетсяпроизвольным графом любого вида, а имеет некоторые особенности. В данной рабо-те предлагаются алгоритмы, которые позволяют использовать эти особенности дляпрактических целей.Рассмотрим взвешенный неориентированный связный граф с неотрицательнымивесами рёбер. Нас интересуют такие его характеристики: центр, радиус и диаметр.Они определяются следующим образом. Эксцентриситет вершины - максимальное израсстояний от данной вершины до других вершин. Радиус графа - минимальный изэксцентриситетов вершин связного графа; вершина, на которой достигается этот мини-мум, называется центральной (центром графа). Диаметр графа - это максимум рас-стояния между вершинами для всех пар вершин. В большинстве случаев эти значениявычисляются вместе с матрицей кратчайших расстояний и соответственно ускорениеих поиска достигается ускорением поиска матрицы кратчайших расстояний для раз-личного рода графов [1-3]. Однако бывают ситуации, когда матрица кратчайших рас-стояний известна, а эти величины нет. Некоторые подобные случаи приведены ниже:- изначально вычислять какую-то из характеристик не требовалось;- матрица кратчайших расстояний графа каким-то образом изменяется, корректи-руется без пересчёта кратчайших расстояний между всеми парами вершин;- требуется вычислять центр, радиус и диаметр не для всего графа, а для некоторогоподграфа. При этом таких подграфов может быть несколько, и они могут изменятьсвой состав.Тривиальный метод отыскания указанных характеристик состоит в просмотре всехэлементов матрицы кратчайших расстояний и определении столбца, максимум значе-ний которого минимален, и максимального элемента матрицы. Сложность нахожденияхарактеристик таким способом составляет O(n2 ) , где n - количество вершин в графе.Если использовать особенности графа, построенного по реальной сети, поиск этихвеличин можно значительно ускорить, применяя следующие алгоритмы.1. Поиск центра, радиуса и диаметра взвешенного графа1.1. А л г о р и т м у с к о р е н н о г о п о и с к а ц е н т р а и р а д и у с аВходные данные алгоритма: матрица кратчайших расстояний M = ( m j ) взвешен-ного неориентированного связного графа с неотрицательными весами ребер.Шаг 1. ПодготовкаИщется пара вершин (x, y), каждая из которых является самой удаленной длядругой:mxy = max mi y = max mi x . (1)i=1,n i=1,nДля этого выбирается любая вершина графа p1, далее ищется вершина p2, для которойmPlP2 = max mp i i . Поиск вершин pj, j = 2 , 3 , . . . , продолжается до тех пор, пока не будетi=1,nвыполнено равенство p J - 1 = pJ+1, тогда x = pj, y = pJ+1.Шаг 2. ПоискРассматриваются все вершины, кроме x, y. Претендент на центр c ищется каквершина, максимум удаления которой от пары (x,y) минимален:max (mc x , mc y ) = min (max (mi x , m i y ) ) . (2)i=1,nПосле нахождения c величина r = max(mc x,mc y ) является первым приближениемрадиуса графа.Шаг 3. ПроверкаИщется периферийная вершина z, такая, чтоmz c = max mi c . (3)i=1,nЕсли mz c = r, то, согласно утверждению 1, r - радиус, c - один из центров графа.Если mz c > r, радиус R графа лежит в пределах r ^ R ^ mz c , переходим к шагу 4.Шаг 4. Попытка замены вершин x и yПроизводится попытка ускорения поиска. Ищется вершина t, для которойmz t > mx y . Если такая вершина найдена, то полагаем x = z, y = t и переходимк шагу 2. Иначе переходим к шагу 5.Шаг 5. Поиск нового претендента на центрСреди нерассмотренных претендентов на центр находится вершина d, для которойmax (mdx, mdy, mdz) = min (max ( m i x , miy, m ^ ) ) . i=1,nЕсли максимальное расстояние от этой вершины до других меньше, чем текущаяверхняя граница радиуса (max mdi < mz c ) , то d - новый претендент на центр. пола-i=1,nгаем c = d, переходим к шагу 3. Если maxmd i = mz c , то c - центр, r - радиус. Еслиi=1,nmax mdi > mz c , то помечаем вершину d как рассмотренную и снова выполняем шаг 5.У т в е р ж д е н и е 1. Пусть дан взвешенный неориентированный связный графс n вершинами и неотрицательными весами рёбер, x и y - две его произвольные вер-шины, вершина c определяется по (2) и вершина z определяется по (3). Тогда еслиmzc = r = max (mcx,mcy), то r - радиус, а c - один из центров графа.Доказательство. Дано: maxmi c = r = min (max (mi x,mi y ) ) . То есть r - макси-i=1,n i=1,nмальное расстояние от c до любой другой вершины, но в то же время r - минимальноерасстояние до одной (а возможно, и обеих) из вершин x, y. Поэтому для любой другойвершины максимум расстояния до вершин из пары (x, y) не меньше r. Следовательно,c - центр (в общем случае не единственный). 1.2. А л г о р и т м б ы с т р о г о п о и с к а д и а м е т р аШаги 1 и 2 алгоритма совпадают с соответствующими шагами алгоритма поискацентра и радиуса.Входные данные алгоритма: матрица кратчайших расстояний M = (mi j ) взвешен-ного неориентированного связного графа с неотрицательными весами рёбер.Шаг 1. ПодготовкаИщется пара вершин (x,y), удовлетворяющая (1). Величина d = mx y при этомявляется текущим претендентом на диаметр.Шаг 2. Поиск опорной вершиныИщется вершина c, удовлетворяющая (2).Шаг 3. Поиск диаметраВыполняется поиск диаметра в столбцах матрицы, соответствующих только темвершинам i, для которых выполнено неравенство mc i > d/2.У т в е р ж д е н и е 2. Пусть дан взвешенный неориентированный связный графс неотрицательными весами рёбер, вершины x, y определяются по (1), вершина c опре-деляется по (2) и d = mx y . Тогда диаметр графа равен d или находится в столбцахматрицы кратчайших расстояний тех вершин i, для которых выполнено неравенствоmci > d/2.Доказательство. Если d = mxy не является диаметром графа, то существуетпара вершин z,t, такая, что mz t > mx y . Для матрицы кратчайших расстояний спра-ведливо mz t ^ mz c + mc t . Следовательно, mx y = d < mz c + mc t , откуда mz c > d/2 илиmc t > d/2. 2. Результаты исследованияПроведено сравнение предложенных алгоритмов быстрого нахождения (БН) с про-стым проходом по матрице кратчайших расстояний (ПМ). В качестве тестовых дан-ных выступали графы, которые используются в транспортных компаниях для расчё-та логистических операций и представляют реальные дорожные сети 20 крупнейшихроссийских городов. Характеристики графов приведеныв таблице. Производилось вы-числение отдельно центра с радиусом, диаметра, а также их совместное нахождение.Вычисления производились несколько раз, в таблице представлены средние значениявремени вычисления. Так как тестовые графы обладают небольшим количеством вер-шин, каждый метод выполнялся 1000 раз и замерялось общее время выполнения. Те-стирование производилось на ПК с процессором Intel Core 2 Duo E8400.Результаты испытаний и характеристики тестовых графовКоличество Центр, радиус Диаметр Центр, радиусвершин и диаметрПМ, с БП, с ПМ, с БП, с ПМ, с БП, с528 1,4 0,015 0,64 0,015 1,5 0,016814 3,5 0,047 1,5 0,031 3,6 0,0311291 8,2 0,047 4,1 0,047 8,4 0,0621302 8,5 0,047 4,1 0,031 8,7 0,0621601 13 0,063 6,2 0,047 13 0,0631641 13 0,23 6,5 0,078 13 0,261645 13 0,13 6,6 0,093 14 0,2031870 18 0,11 8,7 0,078 18 0,132059 21 4,2 10 0,203 22 4,32150 23 0,094 11 0,062 23 0,0942194 24 0,093 12 0,078 25 0,0932280 24 0,16 13 0,109 25 0,2032424 29 0,14 14 0,109 30 0,192484 30 0,81 15 0,109 32 0,832542 31 0,19 16 0,094 32 0,222896 42 0,45 20 0,14 44 0,52921 42 0,109 21 0,094 43 0,162964 42 1,7 21 0,13 43 1,83060 44 0,25 22 0,11 45 0,233364 55 0,23 27 0,204 56 0,28Алгоритм быстрого поиска центра и радиуса справляется с задачей в среднемв 160 раз быстрее, чем простой проход по матрице кратчайших расстояний, ускоре-ние варьируется от 5 до 400 раз. Для поиска диаметра эти цифры - в 100 раз, от 30до 190 раз. для совместного поиска центра, радиуса и диаметра - в 130 раз, от 5 до340 раз.3. К вопросу об особенностях графовЗаметим, что все дорожные сети, на которых проводилось тестирование и проявил-ся значительный эффект от использования алгоритма, представляют собой попыткуохватить заданное количество географических объектов связями с наименьшей сум-марной длиной. То есть особенности этих графов происходят из экономической выго-ды, практического смысла, а также географического расположения и топологическогостроения области размещения сети. Очевидно, что необходима некоторая математи-ческая формализация этих особенностей, которая не только ценна сама по себе, но ипозволит, во-первых, получить критерий определения легко измеряемых графов, во-вторых, понять, за счёт каких свойств графа достигается эффективность алгоритмов.Вынуждены признать, что такой формализации пока сделать не удалось. Уже яс-но, что хорошо известные свойства графа, такие, как планарность и разреженность,не являются необходимыми. В частности, поиск в алгоритме происходит по матри-це кратчайших расстояний, которая, кроме исходного графа, представляет полныйграф с ребрами, веса которых соответствуют элементам матрицы. Аналогично, быст-рое выполнение алгоритма для какого-либо графа вовсе не означает, что он являетсяпланарным. Достаточность этих свойств (планарности и разреженности) также покаобосновать не удалось.Если анализировать выполнение алгоритма, то можно заметить, что скорость по-иска характеристик зависит от выполнения следующего условия. Рассмотрим в ис-следуемом графе все четверки вершин ( i , j , k,l) и все различные треугольники, обра-зуемые каждыми тремя вершинами из этой четверки, A j k , Aj 7 и т.д. Назовем тре-угольник A i j k невырожденным, если во всех комбинациях его вершин для элементовматрицы кратчайших расстояний выполняется mi j + mjk > mik. Рассмотрим четвер-ки вершин (i,j,k,l), у которых все треугольники являются невырожденными. Пустьдля площадей этих треугольников выполняются соотношения S4 ^ S3 ^ S2 ^ S1 иS4 + S1 ~ S3 + S2. Наличие в графе таких четвёрок вершин приводит к замедлению по-иска, и чем таких четверок больше, тем медленнее происходит поиск. Соответственноусловием быстрого поиска характеристик графа является наличие как можно мень-шего числа такого рода четверок. К сожалению, анализ графа на выполнение этогоусловия весьма трудоемок и в вычислительном смысле многократно сложнее выпол-нения самого алгоритма.Таким образом, вопрос строгого определения графовых особенностей, способству-ющих быстрой работе предложенных алгоритмов, остается открытым. На данный мо-мент единственным конструктивным способом проверки графа на эффективность ис-пользования алгоритма является выполнение самого алгоритма.ЗаключениеПредложены точные алгоритмы быстрого поиска центра, радиуса и диаметра взве-шенного графа по матрице кратчайших расстояний. Представленные алгоритмы натестовых графах нашли центр и радиус в среднем в 160 раз, диаметр в 100 раз, асовместно центр, радиус и диаметр в 130 раз быстрее в сравнении с нахождением этихвеличин простым проходом по матрице кратчайших расстояний.Рассматриваемые алгоритмы не гарантируют ускорения вычисления указанных ха-рактеристик в общем случае. Используя условия из п. 3, можно построить граф, на ко-тором ускорения не будет или эффект ускорения будет мал. Однако искусственностьтакого условия позволяет предполагать, что в реальности дорожная сеть, представ-ленная таким графом, не имеет практического смысла.

Ключевые слова

центр графа, радиус графа, диаметр графа, матрица кратчайших расстояний, взвешенный граф, graph center, graph radius, graph diameter, all-pairs shortest path matrix, graph features, weighted graph

Авторы

ФИООрганизацияДополнительноE-mail
Ураков Айрат РенатовичУфимский государственный авиационный технический университеткандидат физико-математических наук, доцентurakov@ufanet.ru
Тимеряев Тимофей ВалерьевичУфимский государственный авиационный технический университетаспирантtimeryaev@yandex.ru
Всего: 2

Ссылки

Johnson D. B. Efficient algorithms for shortest paths in sparse graph // J. ACM. 1977. No. 24. P. 1-13.
Galil Z. and Margalit O. All pairs shortest distances for graphs with small integer length edges // Information and Computation. 1977. No. 134. P. 103-139.
Zwick U. and Shoshan A. All pairs shortest paths in undirected graphs with integer weights // Proc. of the 40th IEEE Symposium on Foundations of Computer Science. Washington: IEEE Computer Society Washington, 1999. P. 605-614.
 Использование особенностей взвешенных графовдля более быстрого определения их характеристик | ПДМ. 2012. № 2(16).

Использование особенностей взвешенных графовдля более быстрого определения их характеристик | ПДМ. 2012. № 2(16).

Полнотекстовая версия