Метод построения многокомпонентной конфигурационной диаграммы сопряжения непроизводных структурных элементов в системе многоуровнеВОго анализа транспортной инфраструктуры

Полный текст

Для разработки многоуровневого информационно-аналитического комплекса анализа транспортной инфраструктуры, используется формально-математический аппарат на основе категорного подхода [1], который предполагает построение автоматизированной имитационной системы (АИС) на базе агрегатного подхода, где согласование моделей различной степени детализации осуществляется с использование операторов сопряженности R. В работе [3] было показано что схеме сопряжения элементов сложной системы может быть поставлен в соответствие геометрический объект, состоящий из правильно соединенных друг с другом симплексов (симплициальных комплексов). С этой целью каждый элемент сложной системы заменяют симплексом, размерность которого равна числу контактов, инцидентных этому элементу, а вершины симплексов, соответствующих сопряженным контактам, отождествляются (склеиваются). Тогда модель транспортной сети, как основы АИС, можно представить как конечную совокупность К двумерных симплексов (минимальных единичных составляющих) некоторого евклидова пространства R2, двумерного комплекса (полиэдра) К. Идея разбиение полиэдра на симплексы прямо следует из определения компонента комплекса. Компонентой некоторого комплекса K называется такой связный его подкомплекс L, что K распадается в сумму непересекающихся подкомплексов L и M. Если K1, …, Kp – совокупность всех компонент комплекса K, то они попарно не пересекаются и в сумме составляют весь комплекс K [4]. В [2] было введено понятие непроизводного структурного элемента (НСЭ) как ограниченной область структуры системы, отличающаяся только ей присущей совокупностью совместно взаимодействующих на категорном уровне свойств простых объектов или единичная составляющая структуры ТС, т.е. симплекса. На структурном непроизводном уровне декомпозиция структуры системы на НСЭ сводится к поиску полных подграфов («клик») графа G=(U, X) . Рассмотрим работу алгоритма декомпозиции графа G=(U, X) более подробно. Основой данной процедуры служит алгоритм 457 Брона-Кэрбоша [5] инициализирующий «клики» по дереву поиска, где каждый узел в дереве соответствует полному подграфу графа, а каждое ребро соответствует вершине графа. Но применив его, например, к графу G=(U, X)(рис. 1) получим набор графов следующего вида ({Vi,Ii},{Vn,In}) которые не являются НСЭ. Рис. 1 - Граф Gk=(U, X), взаимодействия потоков в ТС Следовательно, перед применением алгоритма вводим процедуру подготовки (или доводки исходного графа до графа задающего статическую модель), которая заключается в следующем: в графе G=(U, X) производится поиск всех подграфов Gс’=(U’, X’) представляющих собой цикл Сn где в любой начальной вершине исходящий поток Ii будет связан со входящем потоком Vn конечной вершиной, например для графа G=(U, X) один из таких циклов: I1→ V2→ I2→ V6→ I5→ V5→ I1. Далее для каждого подграфа Gс’=(U’, X’) внедряем новые ребра так, чтобы подграф представляющий собой цикл Сn преобразовался в полный подграф Kn с тем же количеством вершин. Таким образом получаем дополненный граф Gk=(U, X) к которому применяется алгоритм порождения клик. Для графа Gk=(U, X) это следующий набор клик : :[(V1, I1) ─ (V2, I2) ─ (V6, I6 )─ (V5, I5)]; :[(V2, I2) ─ (V3, I3) ─ (V7, I7)─ (V6, I6)]; :[(V3, I3) ─ (V4, I4) ─ (V8, I8 )─ (V7, I7)]; :[(V5, I5) ─ (V6, I6) ─ (V10, I10 )─ (V9, I9)]; :[(V6, I6) ─ (V7, I7) ─ (V11, I11 )─ (V10, I10)]; :[(V7, I7) ─ (V8, I8) ─ (V12, I12 )─ (V11, I11). Далее построим граф =(U, X) , где вершинами являются полученные клики к которому, в свою очередь, так же применим процедуру декомпозиции, результатом которой будет новый набор клик: и . На основании этого набора строится граф =(U, X) являющийся, для рассматриваемого примера, полным (рис.2). Таким образом, получаем иерархическую структурную модель системы, где каждый уровень представляется набором связанных моделей определенной категории, а переход между уровнями определяется операторами сопряженности. В рамках категорийно-функторного подхода, данный класс моделей представляется монадными морфизмами (специальным образом построенные морфизмы в категории индексированных множеств), а их взаимодействие описывается многокомпонентной конфигурационной диаграммой. Рис. 2. Структура взаимодействия графов

Об авторах

Николай Владимирович Губанов

Самарский государственный технический университет

(к.т.н., доцент), заведующий кафедрой «Автоматизация и управление технологическими процессами». 443100, г. Самара, ул. Молодогвардейская, 244

Александр Владимирович Чуваков

Самарский государственный технический университет

(к.х.н.), доцент кафедры «Вычислительная техника» 443100, г. Самара, ул. Молодогвардейская, 244

Егор Юрьевич Кубрин

Самарский государственный технический университет

аспирант 443100, г. Самара, ул. Молодогвардейская, 244

Список литературы

Дополнительные файлы