Автоматика и телемеханика, № 6, 2011
Системный анализ и исследование
операций
© 2011 г. В.К. ПОПКОВ, д-р физ.-мат. наук (Институт вычислительной математики и математической геофизики СО РАН,
Новосибирск)
О МОДЕЛИРОВАНИИ ГОРОДСКИХ ТРАНСПОРТНЫХ СИСТЕМ ГИПЕРСЕТЯМИ
Рассматриваются основные понятия теории б'-гиперсетей. Показано, что на языке этой теории можно описать многие системы сетевой структуры с точностью до адекватного решения поставленных задач. Фактически аналитическая постановка задач анализа и синтеза структур указанных систем является практически имитационной моделью, которую можно использовать для решения задач, связанных с оптимизацией и управлением городских транспортных систем.
1. Введение
В работе рассматриваются основные определения теории й-гиперсетей, приводится классификация отображений ребер вторичных сетей в ветви первичной сети. Дается определение маршрутов в й-гиперсетях. Изобразительные возможности языка теории й-гиперсетей позволяют легко формулировать разнообразные задачи, так или иначе связанные со структурами исследуемых сложных систем. Приведены модели транспортных сетей с учетом мест расположения единиц на проезжей части. Сначала дадим определение простой гиперсети, в которой элементы в виде узла однотипны, а линейные элементы (ветви, ребра) имеют различную природу [1].
2. Основные определения
Шестерка, состоящая из трех множеств и трех отображений й = (X, V, Д; Р, Д, Ш), называется гиперсетью, если Уу € V|Р(у)| =2, Уг € Д|Ш(г)| = 2, Уг € Д множество Д(г) С V составляет маршрут в графе РБ = (X, V). Таким образом, первичная РБ и вторичная ШБ сети гиперсетй й являются графами, а Д отображает ребра ШБ = = (X, Д) в маршруты графа РБ = (X, V).
Так как множество Д(г) является маршрутом, то отображение Д единственным образом определяет отображение Ш. Действительно, концевые вершины маршрута Д(г) являются одновременно концами ребра г, т.е. гиперсеть й можно задать пятеркой (X, V, Д; Р, Д).
В гиперсети вида й = (У, V, Д) узел у С У заменяется графом вида у = {ж*, Д*} структурированной гиперсети, где ж* - ^'-я вершина вторичной сети Шйг, отображенная в узел у структурированной гиперсети йА = (У, V, С^^, Дг)). Таким образом, в отличие от гиперсетей вершины вторичных сетей помещаются в узлы первичной
Рис. 1. Иерархическая 5-гиперсеть Н = (Хо , Хх , Х2 , Хз ,У,Яг, Я2 ,Яз).
сети независимо друг от друга, без ограничения на характер отображения, т.е. возможны варианты отображения нескольких вершин одной вторичной сети в один узел первичной сети.
Дадим формальное определение 5-гиперсети. Пусть задано множество графов (гиперграфов) С0 = (Х0 7У ),С1 = (X1 ,и1),..., Ск = (Xк ,ик) и корневое дерево То = Я), где Z = х0, х1,..., Хк, Я = г1,..., Гк, определяющее вложение графов Gj в С^ (г < 2) аналогично вложениям, определяемым в гиперсетях за тем лишь исключением, что вершины 4 и хj графов С^ и Gj не тождественны, а инцидентны. Очевидно, что одной и той же вершине хк могут быть инцидентны несколько вершин Хк = {хк!' Хк2, • • •, х^ } из I графов {Gjs}, 5 = 1,...,/. На множестве вершин Х3к определяется ^ = (Хк, Е). Вершины х^. и х^5 смежны в и, если соответствующие графы Gj. и Gjs в вершине хк имеют некоторую системообразующую связь I(хji ,Хjs). В противном случае эти вершины не связаны. Так же как в гиперсетях, ребру и\ Е Gj в графе С^ сопоставляется цепь или некоторая связная часть между соответствующими вершинами из С^. На рис. 1 приведен пример такой гиперсети. Из рисунка видно, что вложения графов друг в друга имеют нелинейный характер и полученная таким образом иерархия имеет вид растущего дерева.
Рис. 2. а - структура вложений графов; б - сумма графов всех сетей 5-гиперсети ЕЯ.
В й-гиперсети Н = (^0(63,^2(61))) иерархии вложений будет соответствовать корневое дерево Т(О0) (рис. 2,а).
Необходимо также отметить, что системообразующие связи типа {/(ж, у)}, вообще говоря, могут иметь разную природу и, как правило, существенно зависят от времени. В некоторых случаях, например в системе транспортных сетей разного типа (метро, автобус, трамвай), такими связями в транспортных мультиузлах будут тротуарные линии (пешие переходы). В этом случае имеет смысл рассматривать объединение всех вторичных сетей. Однако для некоторых задач имеет смысл рассматривать сумму всех графов гиперсети Н, включая и первичную сеть РБ, т.е. О = О0 + О1 + ... + О„ + [Ь°}. На рис. 2,б приведен пример объединения всех графов, входящих в й-гиперсеть Н.
Определенную таким образом й-гиперсеть с помощью нижеприведенных матриц можно задать с точностью до изоморфизма или даже до нумерации вершин и ребер.
Графы О*, г = 1,..., к, задаются своими матрицами инцидентности [М* = (с^)}. Вложения графов определяются системой матриц инциденций [М*(а[), Ж*(6р)}, где в матрице М" = 1, если вершина ж; £ О* инцидентна вершине ж4 £ О" (г < и
=0 в противном случае.
В матрице инциденций ребра Ж*(6р) = 1, если ребро ир £ О" вторичной сети инцидентно ветви и^ £ О* первичной сети, и = 0 в противном случае. Представление й-гиперсети заканчивается системой матриц смежности М* = (в^). Пусть вершине ж* £ О* инцидентны вершины [Х"р £ О0р}, тогда матрицы смежности ) определяют смежность этих вершин в ж!^.
Отсюда следует, что й-гиперсеть БИМ = (О0, О1,..., О^) однозначно задается следующей системой матриц:
1. М *(ф) - матрица инциденций графов О*, г = 0, ...,к; /* = 1,...,п*; р* = = 1,..., то*, где (к + 1) - число графов в БИИ, п* - число вершин в графе О*, то* -число ребер в графе О*;
2. [М*Ц ),Л"о*(6*)}, где г,^ = 0,..., к (г < Я; /* = 1,...,п*; Ц = 1,...,п"; й* = 1,...,то*; р" = 1,...,то", - матрицы инциденций, определяющие вложение графов О" в граф О*.
3. М*, (в^) - матрицы смежностей вершин графов вторичных сетей в первичной сети, где г = 0,..., к; г* = 1,..., п*; /, й = 1,..., п, т. е. в1/ =1, если вершины /
и d из графов {Gj} инцидентны вершине х7 и они смежны в этой вершине, иначе зг/ =0.
Вообще говоря, как это кажется с первого взгляда, наибольшее число приложений теории гиперсетей и 5-гиперсетей, вероятно, падает на электросвязь и транспорт. Поэтому большая часть задач, рассматриваемых в данной работе, посвящена именно этим направлениям. Тем не менее уже сейчас видно, что теория 5-гиперсетей применима для анализа и синтеза многих других систем сетевой структуры. Особый интерес вызывают задачи анализа межсетевых структурных взаимодействий сложных систем различной природы.
3. Отображения
В данной работе будут подробно рассмотрены топологические свойства 5-гипер-сетей, которые имеют практическое значение для синтеза и анализа транспортной системы города. Для понимания топологических задач необходимо рассмотреть различные типы вложений вторичных сетей в первичные.
Приведем примеры отображений графов вторичных сетей в первичную сеть (рис. 3,а), имея в виду практическое использование теории при описании и анализе реальных систем сетевой структуры.
5-гиперсети Н = (Ж?, Р£).
При отображении графа вторичной сети Ж? в первичную сеть Р$ возникают четыре класса вложений ребер Ж? в ветви Р$.
Для гиперсети Н = (Р$ Ж?):
1. Ребра вторичной сети Ж? не отображаются в ребра первичной, т.е. отображаются только вершины Ж? в вершины Р$. Таким образом, матрицы (Ьр) в представлении гиперсети отсутствуют (рис. 3,б). Здесь имеет место экс-отображение Ж?э—> Р$ и соответственно экс-гиперсеть.
2. Если ребра вторичной сети Ж? = (X1, Я) идут рядом (параллельно) с ветвями
первичной сети Р$ = (X0, V), то имеет место пара-отображение Ж? — Р$ (рис. 3,в), которое порождает пара-гиперсеть Н = (Ж?, Р£).
WS:
Уг
г\
г3
ЧУ
2 у
'1 У \ У2
д
У2
Рис. 3. Примеры топологических взаимосвязей ребер и вершин различных сетей.
а
2
У
2
У
2
2
У
2
и
У
3
3
3. В случае, когда ребра вторичной сети ШБ располагаются на "плоских" ветвях первичной сети РБ, имеет место экто-отображение \¥БРБ (см. рис. 3,г) и соответственно экто-гиперсеть.
4. В случае рис. 3,д ребра вторичных сетей располагаются внутри ветвей первичной сети. На рис. 3,д приведен пример эндо-отображения ]¥БРБ, которое порождает эндо-гиперсеть.
Вершины также могут по-разному отображаться друг в друга. Для вершин, как и для случая с ребрами, имеем те же четыре способа отображения:
1. Вершина вторичной сети ж абстрактно отображается в вершину у первичной сети, если их взаимное расположение безразлично, т.е. имеет место экс-отображение.
2. Если эта вершина ж отображается рядом с узлом у, то имеет место пара-отображение (см. рис. 1. Вершины 2.1 и 3.1 рядом).
3. При экто-отображении вершин одна вершина располагается на другой. Например, на рис. 1 вершины 2.1 и 3.1 располагаются на узле с номером 1.
4. И наконец, при отображении одной вершины внутрь другой имеет место эндо-отображение вершин. Например, вершина 1.2 располагается внутри вершины 2.1 на рис. 1.
Соответственно й-гиперсети можно называть согласно отображениям элементов. Очевидно, что в одной и той же й-гиперсети разные элементы могут отображаться в другие одновременно разными способами.
Таким образом, словарь теории гиперсетей увеличен за счет особенностей отображения ребер вторичных сетей на ветви первичной сети гиперсети. Действительно, предложенная классификация отображений позволит ставить всевозможные задачи, связанные с описанием, анализом и синтезом сетей различного назначения при различных типах отображения ребер в ветви. Так, для транспортных сетей рассматривается экто-отображение, а для сетей связи - эндо-отображение.
4. Плоские £-гиперсети
Для экто-гиперсетей практическое значение имеет исследование топологических свойств и, в частности, их плоская реализация. Задачи, которые при этом возникают, тесно пересекаются с задачами укладки графов на ориентированные поверхности. Однако специфика гиперсетей и, в частности, й-гиперсетей влечет за собой новые топологические задачи в теории й-гиперсетей.
Пусть задана гиперсеть Н = (РБ, ШБ). Тогда будем говорить, что гиперсеть И РБ-планарна, если граф РБ первичной сети планарен, и гиперсеть И ШБ-планарна, если граф ШБ-планарен. Эти характеристики достаточно изучены в теории г
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.