На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

3
Ожидается:
13 Сентября 2024

Разработка алгоритма пропорционального разделения gh-графа для формирования зон влияния объектов в сложных технических системах

Developing a GH-graph proportional separation algorithm to form of object influence zones in complex technical systems
Дата подачи статьи: 22.03.2023
Дата после доработки: 24.05.2023
Дата принятия к публикации: 02.06.2023
УДК: 004.42+519.178
Статья опубликована в выпуске журнала № 3 за 2023 год. [ на стр. 378-387 ]
Аннотация:В статье предложено одно из возможных решений задачи формирования зон влияния объектов в сложных технических системах. В качестве примера рассматривается система охраны протяженного периметра, исследуется взаимодействие ее объектов (элементов) – мобильных или стационарных объектов охраны, квадрокоптеров, лиц, принимающих решение, возможных потенциальных нарушителей периметра. Причем квадрокоптеры обладают различными техническими характеристиками, в частности, радиусами обзора видеокамер. Для моделирования процесса взаимодействия объектов системы охраны применяется модель на основе нечеткого графа с разнотипными вершинами и множественными и разнотипными связями (GH-графа). В качестве множественных в GH-графе используются связи в виде вектора, объединяющие несколько разнотипных связей в одну. Такая модель позволяет задать все необходимые отношения между элементами системы и при этом обладает преимуществом во времени вычисления расстояний по сравнению с графами, использующими только однотипные и разнотипные связи. Для решения поставленной задачи предлагаются алгоритмические средства моделирования GH-графа, в том числе алгоритм пропорционального разделения графа и средства вычисления его метрик. В работе определена операция разделения GH-графа, сформулированы критерии разделения – пропорциональность подграфов по за-данному параметру и возможность пересечения подграфов. Выполнен синтез алгоритма пропорционального раз-деления GH-графа в соответствии с данными критериями, результаты работы которого показаны на примере рас-смотренной графовой модели. Использование предложенного алгоритма для разделения графа на пропорциональные подмножества и средств вычисления метрических характеристик полученных подграфов позволяет определить зоны влияния объектов системы в соответствии с их техническими параметрами. Рассмотрены возможности программной реализации предложенного алгоритма.
Abstract:The article suggests one of the possible solutions to the problem the object influence zones in complex technical systems (СTS). It considers the extended perimeter security system as a СTS example, investigates the interaction of its objects (elements). The objects of such a system are mobile or stationary security objects, quadrocopters, decision makers, possible potential perimeter violators; provided that quadrocopters have different technical characteristics, in particular, the their video camera surveillance radii differ. To simulate the process of interaction of security system objects, the authors use a model based on a fuzzy graph with different types of vertices and multiple and different types of connections (GH-graph). Multiple connections in the GH-graph are vector connections that combine several different types of connections into one. Such model allows setting all necessary relationships between system elements and at the same time, it has an advantage in the time of calculating distances compared to graphs using only same type and different types of connections. To solve this problem, the authors propose using GH-graph algorithmic modeling means, including the graph proportional separation algorithm and the means of calculating graph metrics. The paper defines the GH-graph splitting operation, defines the separation criteria: the proportionality of subgraphs by a given parameter and the possibility of subgraph intersection. The authors have carried out the synthesis of the GH-graph proportional separation algorithm in accordance with the criteria and shown the algorithm results using the example of the graph model considered. It is shown that using the proposed graph separation algorithm into proportional subsets and the means of calculating the metric characteristics of the obtained subgraphs make it possible to determine the system object influence zones in accordance with their technical parameters. The paper considers the possibilities of software implementation of the proposed algorithm.
Авторы: Мунтян Е.Р. (ermuntyan@sfedu.ru) - Южный федеральный университет (доцент), Таганрог, Россия, кандидат технических наук
Ключевые слова: сложная техническая система, система охраны периметра, множественные связи, разнотипные связи, диаметр, радиус, GH-граф, нечеткий граф, алгоритм разделения графа
Keywords: complex technical system, perimeter security system, multiple edges, different type edges, diameter, radius, GH-graph, fuzzy graph, graph separation algorithm
Количество просмотров: 1886
Статья в формате PDF

Размер шрифта:       Шрифт:

В настоящее время отмечается интерес к исследованию сложных технических систем (СТС) [1], включая задачу планирования совместных действий объектов системы [2]. Для исследования взаимодействия объектов СТС применяют различные подходы, в том числе с использованием графовых моделей [3], метаграфов, гиперграфов и др. [4, 5]. Задача планирования совместных действий объектов СТС требует определения функциональных особенностей каждого из них, а также исследования отношений между объектами и их взаимного влияния.

В данной статье в качестве примера СТС рассмотрим систему охраны протяженного периметра. Ее элементами являются:

– стационарные или мобильные объекты охраны;

– необитаемые интеллектуальные взаимодействующие мобильные роботизированные платформы – квадрокоптеры, предназначенные для сбора данных об объектах охраны;

– потенциальные нарушители охраняемого периметра;

– компьютер (как ЛПР), обрабатывающий  информацию о возможных действиях объектов охраны, квадрокоптеров и нарушителей территории.

Совместное действие всех элементов системы обеспечивает функцию охраны протяженного периметра. Для исследования взаимодействия элементов системы необходимо построить ее конкретную модель и выбрать алгоритмические средства для получения требуемых характеристик. В работе [6] предложен онтологический подход на основе нечетких графов с множественными и разнотипными связями (GH-граф), в качестве предметной области используются СТС. Данное исследование посвящено развитию процесса моделирования систем на основе GH-графов в части разработки алгоритмических средств для решения практических задач предметной области.  GH-граф задан нечеткими множествами вершин и связей. Веса вершин и/или связей соответствуют степеням принадлежности нечетким множествам и могут назначаться экспертом или вычисляться ЛПР путем фаззификации [7, 8].

В таком графе вершины представляют элементы системы, а связи – отношения между ними. В GH-графе вершины являются разнотипными, а множество связей допускает сочетание однотипных, разнотипных и множественных связей в виде вектора. Множественная связь в виде вектора объединяет несколько разнотипных связей, что позволяет уменьшить время вычисления характеристик в GH-графах [9] по сравнению с графами, использующими только однотипные и разнотипные связи [10, 11].

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

Известны различные алгоритмы разделения графов с однотипными связями, которые можно разделить на несколько групп [12]: геометрические, генетические, спектральные, комбинаторные, а также иерархические алгоритмы с учетом многоуровневой оптимизации.

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

Генетические алгоритмы основаны на моделировании генетических процессов биологических организмов. Известно большое количество генетических алгоритмов, применяемых для решения задач дискретной оптимизации,  в том числе для разделения графов [13]. Отмечаются универсальность и простота реализации таких алгоритмов, однако нет гарантии, что за приемлемое время будет найден оптимальный вариант разделения графа. Для спектральных методов разделения графа характерно значительно большее время работы по сравнению с алгоритмами многоуровневой оптимизации [12].

В отличие от геометрических методов группа комбинаторных алгоритмов позволяет учитывать связность вершин, а не их простран- ственное положение. Среди комбинаторных методов можно выделить:

1)    алгоритмы вложенных сечений;

2)    метод деления с учетом связности (LND);

3)    алгоритм Кернигана–Лина и его моди- фикации [14];

4)    алгоритм BLP [15] и др.

В работе [11] сравниваются результаты разделения заданного графа несколькими методами, при этом используются вышеперечисленные методы 2–4 и предложенный алгоритм разделения графа на пропорциональные подграфы на основе алгоритма свертки. Рассматривались и несколько алгоритмов многоуровневой оптимизации [16, 17]. В результате рекомендовано использование предложенного алгоритма разделения графа на основе алгоритма свертки. К преимуществам данного алгоритма можно отнести следующие возможности:

– разделение графа на равные или пропорциональные части;

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

– снижение времени работы разработанного алгоритма до 20 % в зависимости от полноты графа по сравнению с алгоритмами, использующими матрицы смежности или инцидентности и последовательный перебор вершин.

Однако предложенный в работе [12] алгоритм предназначен для разделения неориентированного графа с однотипными связями,  а значит, необходима его модификация, если использовать GH-граф. Для этого следует определить операцию разделения GH-графа и сформулировать критерии работы алгоритма  в зависимости от требований прикладной задачи. Сначала рассмотрим пример модели системы на основе GH-графа.

Модель системы на основе GH-графа

Формально GH-граф задан нечеткими конечными множествами Gʹv и Gʹe [6]:

Gʹ = (Gʹv, Gʹe),                                       (1)

где Gʹv = {gvi | i = 1, 2, ..., n} – множество разнотипных вершин, а Gʹe = {gej | j = 1, 2, ..., m} – множество связей. В качестве связей допускаются ребра и/или дуги (двунаправленные и/или однонаправленные связи) по трем категориям: однотипные, разнотипные (tp – type) и множественные связи в виде вектора `v = , где t – размерность (кратность) вектора `v. Граф представлен списковой структурой, в ко- торой отражена информация не только о логических связях в графе, но и об атрибутах вершин и связей, в частности, типы и веса вершин связей, и др. (все атрибуты указаны в работе [6]).

Будем полагать, что система содержит десять элементов: объекты охраны (ОО1–ОО6), квадрокоптеры (К1, К2), компьютер (ЛПР), потенциальный нарушитель (ПН). При этом технические характеристики квадрокоптеров К1 и К2 различаются: радиус обзора видеокамеры квадрокоптера К1 больше, чем у К2, в 1,5 раза. Тогда модель такой системы в соответствии с (1) будет задана графом Gʹ1 = (Gʹv1, Gʹe1), где  Gʹv1 = {gvi | i = 1, 2, ..., 10} и Gʹe1 = {gej | j =  = 1, 2, ..., 22} (рис. 1). Соответствие элементов и отношений в системе вершинам и связям графовой модели отражено в таблицах 1 и 2.

Поскольку в качестве модели системы используется нечеткий граф, для оценки значения показателей весов вершин и связей графа Gʹ1 необходимо привести их вербальное описание, в рассматриваемом случае это слабый (вес 0,01–0,3), умеренный (вес 0,31–0,7), сильный (вес 0,71–1,0) показатели. С учетом принятой оценки показателей весов вершин и связей графа целесообразно привести некоторые характеристики элементов системы к принятой шкале, например, для квадрокоптера К1 радиус видимости r1 примет значение 0,9 (сильный показатель), а для квадрокоптера К2 радиус r2 равен 0,6 (умеренный показатель), что соответ- ствует заявленным техническим характеристикам этих квадрокоптеров.

Рассмотрим некоторые аспекты модели системы, предложенной на рисунке 1. В графе Gʹ1 ребра типа tp1 соответствуют отношению «Удаленность объектов», например, между объектами ОО1 и ОО2 расстояние может быть определено как небольшое (слабый показатель), следовательно, в модели между вершинами gv1 и gv2 отражено ребро ge1 с весом  µ1 = 0,3. При этом между объектами ОО1 и ОО3 не может быть определено расстояние (так как оно превышает принятую шкалу показателей), следовательно, в модели между вершинами gv1 и gv3 нет связи.

Например, наличие дуги (ge9/tp2) между вершинами gv8 и gv1 на графе Gʹ1 означает, что объект охраны ОО1 находится в зоне видимости квадрокоптера К1. Таким образом, в зоне видимости квадрокоптера К1 находятся элементы системы ОО1, ОО2, ОО3, ОО4 и ПН, что отражено на графе при помощи соответствующих дуг типа tp2 (ge9, ge10, ge11, ge12, ge21). Аналогично в зоне видимости квадрокоптера К2 должны находиться элементы системы ОО3, ОО4, ОО5, ОО6 и ПН.

Так, предложенная модель системы на основе GH-графа позволяет представить все ее необходимые элементы и отношения. Но для решения задачи формирования зон влияния определенных элементов системы (в данном случае – квадрокоптеров) необходимо применение алгоритма разделения GH-графа и средств вычисления его метрик.

Алгоритм пропорционального  разделения GH-графа

Для начала определим понятие «разделение GH-графа». Будем полагать, что разделение GH-графа на n подграфов – это процесс представления исходного графа Gʹ в виде множества вершин Gv = {Gv1, Gv2, …, Gvn} с инцидентными им связями gejÎGe в соответствии  с принятыми критериями, где Gv1, Gv2, …, Gvn – множества вершин n подграфов.

Сформулируем критерии разделения GH-графа, обусловленные требованиями к решению прикладных задач:

– пропорциональность подграфов по заданному параметру (количество или вес вершин, связей и др.);

– наличие или отсутствие пересечений подграфов.

Признак пересечения подграфов Pa определяется следующим образом:

Обоснованность сформулированных критериев разделения GH-графа рассмотрим впоследствии на примере разделения графа Gʹ1.  На рисунке 2 приведена блок-схема алгоритма пропорционального разделения GH-графа на подграфы, в основе которого лежит использо- вание алгоритма свертки графа. В соответствии с данным алгоритмом разделение GH-графа выполняется с учетом сформулированных критериев. Разработанный алгоритм основан на предложенном в работе [12] алгоритме пропорционального разделения неориентированного графа с сохранением значения вычислительной сложности и всех преимуществ оригинального алгоритма.

На предварительном этапе работы алгоритма определяются следующие параметры: количество подграфов part, их пропорциональные доли Pp Î ]0,1[ и признак пересечения подграфов Pa (на соответствие критериям). Затем выполняется коррекция списка графа, которая заключается в фильтрации списка по заданному типу или весу вершин и/или связей. После этого формируются множество доступных вершин графа в текущий момент времени Vertex = {Vertexi | i = 1, 2, ..., (n – 1)} и под- множество выбранных вершин OrVertex =  = {orVertexj | j = 1, 2, ..., l}. В качестве выбранных вершин могут быть вершины заданного типа или принадлежащие группе центральных (или периферийных) вершин и др.

Из подмножества OrVertex при помощи функции cVertexp = getcVertexp (OrVertex) каждый раз определяется одна исходная вершина, пока не будет сформировано подмножество  исходных вершин как CVertex = getCVertex (cVertexp). Полученное подмножество CVertex необходимо для работы алгоритма свертки графа, подробно описанного в работе [12]. Алгоритм свертки использует одну вершину в качестве исходной и позволяет свернуть ее и смежные ей вершины вместе с инцидентными ребрами в одну новую вершину за одну итерацию. Итерации повторяются по необходимости. При этом свернутая часть хранится в виде отдельного списка, что позволяет вернуть граф в первоначальное состояние. В рассматриваемом случае для каждой исходной вершины cVertexp применяется алгоритм свертки графа в параллельном режиме. При этом вместе с исходной вершиной cVertexp поглощаются смежные ей вершины из подмножества Neighbors. Таким образом формируются текущие подмножества вершин подграфов Vertexp.

Рассмотрим пример использования предложенного алгоритма разделения GH-графа и средств вычисления его метрик для решения задачи формирования зон влияния квадрокоптеров. Для вычисления метрик графа рекомендовано использовать стандартные средства, например, описанные в работе [18].

Формирование зон влияния элементов  системы при помощи алгоритма  разделения GH-графа

Система содержит квадрокоптеры с различными техническими характеристиками, поэтому их зоны влияния должны быть пропорциональными (60 % и 40 %). Рассмотрим реализацию предложенного алгоритма разделения GH-графа в программном модуле на примере модели системы, которая представлена в виде графа Gʹ1 [19].

Шаг 1. На начальном этапе определим параметры:

– количество подграфов part = 2 (по количеству квадрокоптеров в системе – К1 и К2);

– пропорциональные доли подграфов P1 = 0,6, P2 = 0,4 (по атрибуту веса связи);

– признак пересечения подграфов Pa = 1.

Шаг 2. Выполним фильтр вершин и связей  в списке графа Gʹ1, оставим вершины типа  tpv1–tpv3 (соответствуют объектам охраны, квадрокоптерам и потенциальному нарушителю) и связи типа tp2 (отношение «наблюдать»), таким образом сформируем текущее множество вершин Vertex.

Шаг 3. В качестве исходных вершин для алгоритма выберем вершины, которые соответствуют квадрокоптерам К1, К2 (cVertex1 = gv8 и cVertex2 = gv9). Тогда подмножество исходных вершин примет вид CVertex = {cVertex1, cVertex2}.

Шаг 4. Сформируем подмножества смежных вершин для ge8 и ge9, получим, соответственно, Neighbors1 = {gv1, gv2, gv3, gv4, gv7} и Neighbors2 = {gv3, gv4, gv5, gv6, gv7}. При этом очевидно, что Neighbors1 ∩ Neighbors2 = {gv3, gv4, gv7}.

Шаг 5. Выполним алгоритм свертки графа в параллельном режиме, начиная с исходных вершин ge8 и ge9. Поскольку Neighbors1 ∩  ∩ Neighbors2 ≠ ø, отрабатывается функция распределения вершины из множества Vertex в подмножества Vertex1 и Vertex2 в соответствии с критериями разделения, как показано на рисунке 2, Vertexp = getVertex (Pp, Pa).

Шаг 6. Сформируем подмножества вершин подграфов Vertex1 = {ge1, ge2, ge3, ge4, ge7, ge8} и Vertex2 = {ge3, ge4, ge5, ge6, ge7, ge9}. Алгоритм свертки заканчивает свою работу, так как смежных вершин для вершин из этих подмножеств больше нет. Поскольку все вершины из множества Vertex распределены в подмножества Vertex1 и Vertex2, переходим на шаг 7.

Шаг 7. Оптимизируем полученный результат. Поясним этот шаг подробнее. Вес связи типа tp2 (отношение «Наблюдать») характеризует степень удаленности квадрокоптера и объекта охраны. Для вершин из подмножества Neighbors1 веса связей распределяются следующим образом: µ9 = 0,5, µ10 = 0,9, µ11 = 0,8,  µ12 = 0,9, µ21 = 0,8 (максимальное числовое значение – 0,9), а для вершин из подмножества Neighbors2 веса связей µ13 = 0,6, µ14 = 0,3,  µ15 = 0,5, µ16 = 0,6, µ22 = 1,0 (максимальное числовое значение – 1,0). Очевидно, что в соответствии с принятыми значениями радиусов обзора видеокамер квадрокоптеров К1 и К2 (r1 = 0,9  и r2 = 0,6) объект охраны ОО3 не попадает в зону видимости квадрокоптера К2, поэтому вершина gv3 должна быть исключена из подмножества Vertex2 в соответствии с принятыми критериями.

Тогда подмножества вершин подграфов примут значения Vertex1 = {ge1, ge2, ge3, ge4, ge7, ge8} и Vertex2 = {ge4, ge5, ge6, ge7, ge9}. Результат разделения графа Gʹ1 представлен на рисунке 3.

Полученные таким образом подмножества вершин подграфов Vertex1 и Vertex2 позволяют сформировать зоны влияния квадрокоптеров К1 = {ОО1, ОО2, ОО3, ОО4, ПН} и К2 = {ОО4, ОО5, ОО6, ПН} в заданных пропорциях. Вычисление метрик полученных подграфов (радиус, диаметр) позволяет определить соответствие зоны влияния техническим параметрам элементов системы, в рассматриваемом случае диаметр подграфа не должен превышать радиус обзора видеокамеры квадрокоптера (в принятой шкале). Пересечение зон влияния квадрокоптеров в системе обусловлено необходимостью соблюдения жизненного цикла каждого устройства, например, временные рамки работоспособности, необходимость в подзарядке и т.д. Очевидно, что с учетом жизненного цикла для обеспечения функций охраны заданного периметра достаточно трех квадрокоптеров.

Программная реализация

Программный модуль [19], реализующий предложенный алгоритм разделения и средства вычисления характеристик графа, встроен в программный комплекс моделирования системы на основе GH-графа (ПК), как показано на рисунке 4.

Для создания графического изображения используется блок редактирования графа. Сразу после загрузки (посредством блока загрузки графа) или по мере создания графа определяются его основные параметры. Полученный граф сохраняется в блоке хранения графа в виде .xml-файла, в котором хранится его списковое представление, и посредством блока отображения выводится на экран. Блок вычисления характеристик графа и блок реализации алгоритма разделения графа составляют программный модуль реализации алгоритмов графа.

ПК разработан на языке C++ с использованием библиотеки Qt. Все используемые средства реализации являются кроссплатформенными, что обусловливает возможность функционирования ПК в различных операционных системах. Разработанный программный модуль планируется использовать с применением SQL или NoSQL БД, например, графовой СУБД Neo4j и других БД [20].

Заключение

В работе поставлена задача синтеза формирования зон влияния объектов в сложных технических системах, для решения которой предложен алгоритм пропорционального разделения графа с множественными и разнотипными связями (GH-графа). Приведено формальное описание такого графа, рассмотрен пример модели на основе GH-графа фрагмента конкретной системы охраны протяженного периметра, которая содержит ряд объектов (элементов) – это объекты охраны, квадрокоптеры, ЛПР (компьютер) и нарушитель периметра, причем квадрокоптеры обладают различными техни- ческими характеристиками, в частности, различаются радиусы обзора их видеокамер. Такая модель позволяет задать все необходимые отношения между элементами системы и при этом обладает преимуществом во времени вычисления расстояний по сравнению с графами, использующими только однотипные и разнотипные связи.

Определена операция разделения GH-графа, сформулированы критерии разделения, в том числе пропорциональность подграфов по заданному параметру (количество или вес вершин, связей и др.) и возможность пересечения подграфов.

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

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

Выполнена программная реализация модуля, содержащего алгоритм разделения графа на пропорциональные подмножества и средства вычисления метрик, интегрированного в программный комплекс моделирования системы на основе GH-графа. Реализованная в програм- мном комплексе модель СТС на примере системы охраны, а также использование предложенного алгоритма для разделения графа на пропорциональные подмножества и средства вычисления метрических характеристик полученных подграфов (радиус, диаметр) позволяют определить зоны влияния объектов системы в соответствии с их техническими параметрами.

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

1.    Коноваленко С.А., Шабля В.О., Титов Г.О. Анализ методов контроля состояния процесса функционирования сложных технических систем // Наукосфера. 2021. № 12-2. С. 224–230.

2.    Дубровина А.И. Состав инженерной защиты и технической охраны объектов // Modern Sci. 2020. № 12-3. С. 236–241.

3.    Буравцев А.В., Щенников А.Н. Проектирование данных для компьютерной обработки в фискальных системах // ИТНОУ. 2018. № 1. С. 3–14.

4.    Плесневич Г.С., Тарасов В.Б. Метаграфы с темпорально-логическими ограничениями // ИММВ-2021: сб. науч. тр. 2021. С. 201–219.

5.    Миков А.И., Миков А.А. Динамические гиперграфы процессов восстановления мобильных сетей // Информатизация и связь. 2021. № 5. С. 31–38. doi: 10.34219/2078-8320-2021-12-5-31-38.

6.    Еремеев А.П., Мунтян Е.Р. Разработка онтологии на основе графов с множественными и разнотипными связями // Искусственный интеллект и принятие решений. 2021. № 3. С. 3–18. doi: 10.14357/20718594210301.

7.    Minaev Y.N., Filimonova O.Y., Minaeva J.I., Filimonov A. Fuzzy mathematics with limited possibilities for assigning membership functions. Cybernetics and Systems Analysis, 2020, vol. 56, no. 1, рр. 29–39. doi: 10.1007/s10559-020-00218-9.

8.    Дандыбаев С.Т. Нечеткие множества с нечеткими функциями принадлежности // Теория и практика современной науки. 2021. № 1. С. 130–133.

9.    Мунтян Е.Р. Реализация нечеткой модели взаимодействия объектов сложных технических систем на основе графов // Программные продукты и системы. 2019. Т. 32. № 3. С. 411–418. doi: 10.15827/0236-235X.127.411-418

10.  Smirnov A.V. Spanning tree of a multiple graph. J. of Combinatorial Optimization, 2021, vol. 43, no. 4, pp. 850–869. doi: 10.1007/s10878-021-00810-5.

11.  Кальней А.М. Модели многоуровневых сетей (краткий обзор) // Проблемы информатики. 2021. № 3. С. 5–20.

12.  Сергеев Н.Е., Мунтян Е.Р. Применение алгоритма свертки для разделения графа на пропорциональные подграфы // Вестн. УГАТУ. 2018. Т. 22. № 1. С. 121–130.

13.  Akhand M.A.H., Ayon S.I., Shahriar S.A., Siddique N. Discrete spider monkey optimization for travelling salesman problem. Applied Soft Computing, 2020, vol. 86, art. 105887. doi: 10.1016/j.asoc.2019.105887.

14.  Fiduccia C.M., Mattheyses R.M. A linear-time heuristics for improving network partitions. Proc. 19th Design Automation Conf., 1982, pp. 175–181. doi: 10.1109/DAC.1982.1585498.

15.  Moussawi А.El., Ruiz R.R., Seghouani N.B. Sampling-based label propagation for balanced graph partitioning. Proc. ACM/SPEC on ICPE, 2022, pp. 223–230. doi: 10.1145/3489525.3511698.

16.  Курейчик В.В., Заруба Д.В. Двухуровневый алгоритм разбиения графа на части // Изв. ЮФУ. Технич. науки. 2019. № 2. С. 6–15.

17.  Курейчик В.В., Курейчик Вл.Вл. Программная подсистема для решения NP-сложных комбинаторно-логических задач на графах // Изв. ЮФУ. Технич. науки. 2021. № 2. С. 39–50.

18.  Muntyan E.R., Melnik E.V. The graph-based analysis of structural delays in distributed multiprogram systems of information processing. JPCS, 2020, vol. 1661, no. 1, art. 012061. doi: 10.1088/1742-6596/1661/1/012061.

19.  Мунтян Е.Р. Программный модуль для моделирования взаимодействия акторов и групп акторов на основе графов: Свид. о регистр. ПрЭВМ № 2018665593. Рос Федерация, 2018.

20.  Еремеев А.П., Панявин Н.А. Унификация модели представления данных и преобразование форматов на основе нереляционной СУБД Neo4j // Программные продукты и системы. 2022. Т. 35. № 4. С. 549–556.
doi: 10.15827/0236-235X.140.549-556.

Reference List

1. Konovalenko, S.A., Shablya, V.O., Titov, G.O. (2021) ‘Analysis of methods for control of the condition of the functioning process of complex technical systems’, Naukosfera, (12-2), pp. 224–230 (in Russ.).

2. Dubrovina, A.I. (2020) ‘A composition of engineering protection and technical protection of facilities’, Modern Sci., (12-3), pp. 236–241 (in Russ.).

3. Buravtsev, A.V., Schennikov, A.N. (2018) ‘Designing data for computer processing in fiscal systems’, ITNOU, (1), pp. 3–14 (in Russ.).

4. Plesnevich, G.S., Tarasov, V.B. (2021) ‘Metagraphs with temporal-logical constraints’, Proc. Integrated Models and Soft Computing in Artificial Intelligence, pp. 201–219 (in Russ.).

5. Mikov, A.I., Mikov, A.A. (2021) ‘Dynamic hypergraphs of renewal processes in mobile networks’, Informatization and Communication, (5), pp. 31–38 (in Russ.). doi: 10.34219/2078-8320-2021-12-5-31-38.

6. Eremeev, A.P., Muntyan, E.R. (2021) ‘Development of an ontology based on graphs with multiple edges of different types’, Artificial Intelligence and Decision Making, (3), pp. 3–18 (in Russ.). doi: 10.14357/20718594210301.

7. Minaev, Y.N., Filimonova, O.Y., Minaeva, J.I., Filimonov, A. (2020) ‘Fuzzy mathematics with limited possibilities for assigning membership functions’, Cybernetics and Systems Analysis, 56(1), рр. 29–39. doi: 10.1007/s10559-020-00218-9.

8. Dandybaev, S.T. (2021) ‘Fuzzy sets with fuzzy membership functions’, Theory and Practice of Modern Sci., (1), pp. 130–133 (in Russ.).

9. Muntyan, E.R. (2019) ‘Implementation of a fuzzy model of interaction between objects in complex technical systems based on graphs’, Software & Systems, 32(3), pp. 411–418 (in Russ.). doi: 10.15827/0236-235X.127.411-418.

10. Smirnov, A.V. (2021) ‘Spanning tree of a multiple graph’, J. of Combinatorial Optimization, 43(4), pp. 850–869. doi: 10.1007/s10878-021-00810-5.11.  Kalney, A.M. (2021) ‘Layered network models (overview)’, Problems of Informatics, (3), pp. 5–20 (in Russ.).

12. Sergeev, N.E., Muntyan, E.R. (2018) ‘Using convolution algorithm to separate a graph on the proportional subgraphs’, Vestn. USATU, 22(1), pp. 121–130 (in Russ.).

13. Akhand, M.A.H., Ayon, S.I., Shahriar, S.A., Siddique, N. (2020) ‘Discrete spider monkey optimization for travelling salesman problem’, Applied Soft Computing, 86, art. 105887. doi: 10.1016/j.asoc.2019.105887.

14. Fiduccia, C.M., Mattheyses, R.M. (1982) ‘A linear-time heuristics for improving network partitions’, Proc. 19th Design Automation Conf., pp. 175–181. doi: 10.1109/DAC.1982.1585498.

15. Moussawi, А.El., Ruiz, R.R., Seghouani, N.B. (2022) ‘Sampling-based label propagation for balanced graph partitioning’, Proc. ACM/SPEC on ICPE, pp. 223–230. doi: 10.1145/3489525.3511698.

16. Kureychik, V.V., Zaruba, D.V. (2019) ‘Two-level graph partitioning algorithm’, Izv. SFedU. Engineering Sci., (2), pp. 6–15 (in Russ.).

17. Kureychik, V.V., Kureychik, Vl.Vl. (2021) ‘Software subsystem for solving np-complex combinatorial logic problems on graphs’, Izv. SFedU. Engineering Sci., (2), pp. 39–50 (in Russ.).

18. Muntyan, E.R., Melnik, E.V. (2020) ‘The graph-based analysis of structural delays in distributed multiprogram systems of information processing’, JPCS, 1661(1), art. 012061. doi: 10.1088/1742-6596/1661/1/012061.

19. Muntyan, E.R. (2018) A Software Module for Modeling the Interaction of Actors and Actors Groups Based on Graphs, Pat. RF, № 2018665593.

20. Eremeev, A.P., Paniavin, N.A. (2022) ‘Unification of a data presentation model and format conversion based on a non-relational Neo4j DBMS’, Software & Systems, 35(4), pp. 549–556 (in Russ.). doi: 10.15827/0236-235X.140.549-556.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=5012
Версия для печати
Статья опубликована в выпуске журнала № 3 за 2023 год. [ на стр. 378-387 ]

Возможно, Вас заинтересуют следующие статьи схожих тематик: