Нужен граф дорог России — что делать/с чего начать? / users: Russia / OpenStreetMap Forum

Граф дорожного движения — единый геоинформационный набор данных, описывающий транспортную инфраструктуру и ее основные параметры на всю территорию России, стран СНГ и Мира.
Единый граф движения содержит описание:

  • улично-дорожной сети (УДС);
  • проездов по рилегающим территориям (внутриквартальные проезды, проезды в промзонах, торгово развлекательных комплексов и пр.)
    железных дорог федерального и ведомственного значения;
  • трамвайных путей;
  • линий метрополитена;
  • пешеходных дорог;
  • организации движения внутри зданий (indoor).
  • транспортных объектов (ЖД станции и платформы, станции метрополитена, аэропорты, пристани и порты).

Описание УДС содержит информацию о названиях и типах улиц, трасс и магистралей, административной привязке объектов, о разрешенной скорости и направлении движения, расположении километровых столбов, типе дорожного покрытия, запрещенных маневрах и т.д.

Слои, описывающие расположение железных дорог, сопряжены со следующими отраслевыми справочниками железнодорожного транспорта России:

  • Автоматизированная система управления железнодорожным транспортом (АСУЖТ);
  • Единая сетевая разметка (ЕСР);
  • АСУ «Экспресс».

Единый граф движения является постоянно поддерживаемым и развивающимся продуктом, в основе его обновлений лежит комплексная работа по приему, обработке и исправлению ошибок и замечаний, поступающих от пользователей; по анализу и обработке многочисленных материалов, включая дешифрирование космических снимков высокого разрешения и результатов обследований на местности, в том числе проводимых собственными полевыми бригадами ЗАО «Геоцентр-Консалтинг».

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

Информация о полном списке атрибутов единого графа движения и возможности его технологического тестирования доступна по запросу.


Подобрать решение под требуемые задачи и получить консультацию помогут специалисты нашей компании по телефону или электронной почте.

+7 (495) 620-70-51

sale@digimap.ru

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

Для неориентированного простого графа (рёберная)[1]плотность графа определяется как

.

Максимальное число рёбер равно ½ |V| (|V|−1), так что максимальная плотность равна 1 (для полных графов) и минимальная равна 0[2].

Верхняя плотность

Верхняя плотность — это расширение понятия плотности графа с конечных графов на бесконечные. Интуитивно понятно, что бесконечный граф имеет произвольно большие конечные подграфы с любой плотностью, меньшей верхней плотности, и не имеет произвольно больших конечных подграфов с плотностью, большей верхней плотности. Формально, верхняя плотность графа G — это нижняя грань таких значений α, что конечные подграфы графа G с плотностью больше α имеют ограниченный порядок. Используя теорему Эрдёша — Стоуна[en] можно показать, что верхняя плотность может быть только 1 или одним из значений последовательности 0, 1/2, 2/3, 3/4, 4/5, … n/(n + 1), … (см, например, Дистель. Упражнения к главе 7[1]).

Разреженные и тугие графы

Штрейну[3] и Теран[4] определяют граф как (k,l)-разреженный, если любой непустой подграф с n вершинами имеет максимум kn − l рёбер, и как (k,l)-тугой, если он (k,l)-разреженный и имеет в точности kn − l рёбер. Таким образом деревья в точности (1,1)-тугие графы, леса – в точности (1,1)-разреженные графы, а графы с древесностью[en]k — в точности (k,k)-разреженные графы. Псевдолеса[en] — это в точности (1,0)-разреженные графы, а Ламановы графы, появляющиеся в теории жёсткости[en], это в точности (2,3)-тугие графы.

Другие семейства графов также могут быть описаны подобным образом. Например, из того, что любой планарный граф с n вершинами имеет максимум 3n — 6 ребра, и что любой подграф планарного графа является планарным вытекает, что планарные графы являются (3,6)-разреженными графами. Однако не всякий (3,6)-разреженный граф будет планарным. Аналогично, внешнепланарные графы являются (2,3)-разреженными и планарные двудольные графы являются (2,4)-разреженными.

Штрейну и Теран показали, что проверка является ли граф (k,l)-разреженным, может быть выполнена за полиномиальное время.

Разреженные и плотные классы графов

Оссона и Нешетрил[5] полагают, что при делении на разреженные/плотные графы необходимо рассматривать бесконечные классы графов, а не отдельных представителей. Они определили местами плотные классы графов как классы, для которых существует такой порог t, что любой полный граф появляется как t-подраздел в подграфе графов класса. И наоборот, если такой порог не существует, класс называется нигде не плотным. Свойства деления на местами плотные/нигде не плотные обсуждается в статье Оссона и Нешетрил[6].

Примечания

  1. 12Рейнгард Дистель. Теория графов. — Новосибирск: Издательство института математики, 2002. — ISBN 5-86134-101-X.
  2. Thomas F. Coleman, Jorge J. Moré Estimation of sparse Jacobian matrices and graph coloring Problems // SIAM Journal on Numerical Analysis. — 1983. — Т. 20, вып.

    1. — С. 187—209. — DOI:10.1137/0720013.

  3. Audrey Lee, Ileana Streinu Pebble game algorithms and sparse graphs // Discrete Mathematics. — 2008. — Т. 308, вып. 8. — С. 1425—1437. — DOI:10.1016/j.disc.2007.07.104.
  4. I. Streinu, L. Theran Sparse hypergraphs and pebble game algorithms // European Journal of Combinatorics. — 2009. — Т. 30, вып. 8. — С. 1944—1964. — DOI:10.1016/j.ejc.2008.12.018. — arXiv:math/0703921.
  5. Patrice Ossona de Mendez, Jaroslav Nešetřil European Congress of Mathematics. — European Mathematical Society, 2010. — С. 135—165.
  6. Jaroslav Nešetřil, Patrice Ossona de Mendez Sparsity: Graphs, Structures, and Algorithms. — Heidelberg: Springer, 2012. — Т. 28. — ISBN 978-3-642-27874-7. — DOI:10.1007/978-3-642-27875-4.

Литература

  • Paul E. Black, Sparse graph, from Dictionary of Algorithms and Data Structures, Paul E. Black (ed.), NIST. Retrieved on 29 September 2005.
  • Preiss. Data Structures and Algorithms with Object-Oriented Design Patterns in C++. — John Wiley & Sons, 1998. — ISBN 0-471-24134-2.

Справка по ИДЗ «Графы»

Скелет графа общего вида. В случае, когда при исследовании графа L=(X.U;P) общего вида требуется не полная информация о нём, а лишь знание того, какие пары его различных вершин смежны и какие нет, прибегают к носителю такой информации – скелету графа L, который обозначим как .

Граф относится к классу обыкновенных графов с множеством вершин тем же, что и в графе L, и новым множеством рёбер , определённым следующим образом:

1) если в графе L есть петли, то они удаляются;

2) если в графе L есть дуги, то производится дезориентация дуг;

3) если в графе L есть кратные рёбра, то они заменяются одним эквивалентным ребром-звеном;

4) оставшиеся рёбра образуют множество рёбер .

Таким образом, множество рёбер состоит из рёбер, полученных из множества U после выполнения описанных выше процедур 1, 2, 3.

Определение числа маршрутов длины «L» на графе

Маршрутом mi,j в графе G=(X,U) называется конечная последовательность вершин и рёбер вида –

m0,l =( x0,u1,x1,u2,x2,…,xl–1,uk, xl ),

где x0, xl – соответственно начальная и конечная вершины маршрута m0,l .

Очевидно, в конечном графе G=(X,U) можно выделить только конечное число маршрутов.

Длина маршрута mi,j равна числу рёбер, которые в него входят.

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

Для определения маршрутов длины q в графе G=(X,U) его матрицу смежности R возводят в степень, равную q. Тогда для каждого значения степени q=1,2,…,k значение элемента (ri,j)q матрицы Rq определяет количество маршрутов mi,j длиной, равной значению степени q.

Рисунок 3

ПРИМЕР. Для графа G= (X,U) , представленного на рисунке 3, определить количество маршрутов длины, равной 2.

Матрица смежности R графа G имеет вид:

R=

  X1 X2 X3 X4
X1
X2
X3
X4

Возведем матрицу R в квадрат:

 

R2=

  X1 X2 X3 X4
X1
X2
X3
X4

 

Значение каждого элемента ri,j матрицы R2 равно числу маршрутов длины 2, ведущих из вершины xi в вершину xj.

Например, r3,2=2 означает, что в графе два маршрута длины 2, которые ведут из вершины x3 в вершину x2 . Запишем их:

m3,2=x3,3,x1,1,x2; m3,2 =x3,4,x4,2,x2.

Задание 4.

Для графа, представленного на рисунке 1 выполнить следующее:

4.1. Привести примеры подграфов 3-х вершинных, 4-х вершинных, 1-вершинных.

4.2.

Привести пример суграфа данного графа.

 

4.3. Выполнить унарные операции для вершин, помеченных *.

Задание 5.

Для графа G=(X,U) ( рисунок 1) выполнить следующее:

5.1. Построить матрицу метрики (отклонений).

5.2. Вычислить радиус и диаметр.

5.3. Определить периферийные точки.

Способ нахождения метрики графа

Для нахождения метрики = графа L = (X,U) достаточно знать его матрицу смежности R={ ri,j} над булевой алгеброй B = ( 0,1 ), т.е. элементы матрицы ri,j = 1, если вершины xi и xj – смежны и ri,j = 0, в противном случае, все действия над элементами матрицы R производятся по правилам логической алгебры:

1 + 1 = 1; 0 + 0 = 0; 1 + 0 = 1; 0 * 0 = 0; 1 * 0 = 0.

Сопоставляя уже известные нам способы для установления существования маршрутов в графе длины q = m, можно утверждать, что при возведении в степень матрицы S = R + E, где Е – единичная матрица той же размерности, что и размерность матрицы R, на некотором шаге возведения в степень получим:

S= Sk+1, т.е. устойчивую матрицу S в степени «k».

Значения степеней p матрицы Sp: p= {k, k–1, k–2, … , 1} равны длинам простых кратчайших цепей, связывающих вершины xi и xj.

Таким образом, последовательно возводя в степень p = {1, 2, 3,…, k} матрицу S до получения устойчивой матрицы Sk, можно определить расстояния между всеми вершинами графа L=(X,U), построив матрицу метрики графа L.


Читайте также:

С помощью алгоритма фронта волны найти расстояния в ориентированном графе D: диаметр, радиус и центры.

Пусть ориентированный граф с n³2 вершинами и V,W (V¹W) – заданные вершины из V.

Алгоритм поиска минимального пути из в в ориентированном графе

(Алгоритм фронта волны).

1) Помечаем вершину индексом 0, затем помечаем вершины Î образу вершины индексом 1.

Обозначаем их FW1 (V). Полагаем K=1.

2) Если или K=N-1, и одновременно то вершина не достижима из . Работа алгоритма заканчивается.

В противном случае продолжаем:

3) Если , то переходим к шагу 4.

В противном случае мы нашли минимальный путь из в и его длина равна K. Последовательность вершин

Есть этот минимальный путь. Работа завершается.

4) Помечаем индексом K+1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом K. Множество вершин с индексом K+1 обозначаем . Присваиваем K:=K+1 и переходим к 2).

Замечания

· Множество называется фронтом волны KГо уровня.

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

Чтобы найти расстояния в ориентированном графе, необходимо составить матрицу расстояний R(D) между его вершинами. Это квадратная матрица размерности , элементы главной диагонали которой равны нулю (, I=1,..,N).

Сначала составляем матрицу смежности. Затем переносим единицы из матрицы смежности в матрицу минимальных расстояний (, если ). Далее построчно заполняем матрицу следующим образом.

Рассматриваем первую строку, в которой есть единицы. Пусть это строка − I-тая и на пересечении с J-тым столбцом стоит единица (то есть ). Это значит, что из вершины можно попасть в вершину за один шаг. Рассматриваем J-тую сроку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент . Тогда из вершины в вершину можно попасть за два шага. Таким образом, можно записать . Следует заметить, что если в рассматриваемых строках две или более единиц, то следует прорабатывать все возможные варианты попадания из одной вершины в другую, записывая в матрицу длину наикратчайшего из них.

Примечание. Самый длинный путь найти при помощи алгоритма фронта волны.

Пример

Найдем расстояния в ориентированном графе D, изображенном на рис. 7. В данной задаче количество вершин N=7, следовательно, матрицы смежности и минимальных расстояний между вершинами ориентированного графа DБудут иметь размерность 7×7.

Рис.7.

Матрица смежности:

.

Начинаем заполнять матрицу R(D) минимальных расстояний: сначала ставим нули по главной диагонали и Rij=Aij, если Aij=1, (т. е. переносим единицы из матрицы смежности). Рассматриваем первую строку. Здесь есть две единицы, то есть из первой вершины за один шаг можно попасть во вторую и шестую. Из второй вершины можно попасть за один шаг в третью (путь в первую вершину нас не интересует), следовательно, можно записать . Из шестой вершины можем добраться за один шаг в пятую и седьмую, а значит, , . Теперь ищем маршруты, исходящие из первой вершины, состоящие из 3 шагов: за 2 шага идем в третью вершину, оттуда за один шаг попадаем в четвертую, поэтому . В итоге получаем следующую матрицу:

.

Таким образом, диаметром исследуемого ориентированного графа будет .

Для каждой вершины заданного ориентированного графа найдем максимальное удаление (эксцентриситет) в графе G от вершины нее по формуле, которая была приведена выше : R(Vi) − максимальное из расстояний, стоящих в I-той строке. Таким образом,

R(V1)=3, R(V2)=3, R(V3)=5, r(V4)=4, r(V5)=2, r(V6)=2, r(V7)=3.

Значит, радиусом графа G будет

Соответственно, центрами графа GБудут вершины V5 и V6 , так как величины их эксцентриситетов совпадают с величиной радиуса.

Опишем теперь нахождение минимального пути из вершины V3 в вершину V6 по алгоритму фронта волны. Обозначим вершину V3 как V0, а вершину V6 — как W (см. рис. 8).

Рис.8.

Множество вершин, принадлежащих образу V0, состоит из одного элемента — это вершина V4, которую, согласно алгоритму, обозначаем как V1: FW1(V3)={V4}.

Поскольку искомая вершина не принадлежит фронту волны первого уровня , продолжаем работу алгоритма. Строим фронт волны второго уровня — это множество вершин, принадлежащих образу вершины V1: FW2(V3)={V7}, обозначаем V7≡V2. В образ вершины V2 входят две вершины — V5 и V4, но, так как V4 уже была помечена как V0, то фронт волны третьего уровня состоит из одного элемента: FW3(V3)={V5}, V5≡V3. Из непомеченных вершин в образ вершины V3 входят V1 и V2, соответственно, FW4(V3)={V1, V2}, V1≡V4, V2≡V4. Теперь помечены все вершины, кроме V6, которая входит в образ вершины , то есть FW5(V3)={V6≡W}, работа алгоритма закончена. Минимальный путь (5 шагов) из вершины V3 в вершину V6: V3 V4 V7 V5 V1V6.

Добавить комментарий

Закрыть меню