Метод поиска разрезов графа для задачи управления инженерной инфраструктурой

Автор(ы): Вандиловская П.А., Крыгин А.А., Лукинова О.В., Рощин А.А.

Выпуск: 111

Рубрика: Управление техническими системами и технологическими процессами

Год: 2024

Библиография: Вандиловская П.А., Крыгин А.А., Лукинова О.В., Метод поиска разрезов графа для задачи управления инженерной инфраструктурой // Управление большими системами. Выпуск 111. М.: ИПУ РАН, 2024. С.226-246. DOI: https://doi.org/10.25728/ubs.2024.111.9

Дата опубликования: 30.09.2024

Ключевые слова: разрез графа, мультиразрез, инженерная сеть, свободный путь графа

Аннотация: Целью функционирования инженерных сетей является обеспечение поставок того или иного ресурса потребителю, при этом, в идеальном случае, подача должна быть непрерывной, что напрямую зависит от целостности инфраструктуры сети. Однако различные факторы: атаки злоумышленников, природные катаклизмы, наконец, естественные технологические причины (различные аварии), приводят к отключению некоторых участков сети, что влечет нарушение режима поставки ресурса. Тогда возникает задача поиска наиболее уязвимых (критических), с точки зрения возможного ущерба, участков инженерной сети. Ее решение позволяет принять соответствующие меры по защите сети от влияния негативных факторов и обеспечить максимально бесперебойную подачу ресурсов. Инженерную сеть принято моделировать графовыми структурами, поэтому одним из методов решения данной задачи является нахождение разрезов графа сети. Такие методы существуют, но все они обладают рядом ограничений. В данной работе предлагается новый метод нахождения всех разрезов графа инженерной сети, вообще говоря, произвольной размерности; описывается алгоритм метода, а также его теоретическое обоснование. Концепция метода основана на формировании на каждой итерации особых конструкций графа (мультиразрезов) таким образом, что в результате отработки алгоритма метода осуществляется поиск всех разрезов. Примерами инженерных сетей, где данный метод может быть использован в качестве одного из инструментов принятия рациональных решений при эксплуатации сетевых объектов, являются электросети, сети водоснабжения и канализации, а также сети связи и телекоммуникаций.

Author(s): Vandilovskaya P., Krygin A., Lukinova O., Roschin A.

Article title: Method for finding cuts for engineering infrastructure management tasks

Issue: 111

Year: 2024

Keywords: graph, cut, multicuts, engineering network, free path in graph

Abstract: The goal of the functioning of engineering networks is to ensure the delivery of a particular resource to a consumer, ideally with uninterrupted supply which directly depends on the integrity of the network infrastructure. However, various factors such as attacks by malicious actors, natural disasters, and technological accidents can lead to the disconnection of certain parts of the network, resulting in the disruption of resource delivery. This necessitates the task of identifying the most vulnerable parts of the engineering network in terms of potential damage, which allows appropriate measures to be taken to protect the network from negative factors and ensure maximum uninterrupted resource delivery. Engineering networks are commonly modeled as graph structures, therefore one method of solving this task is to find the cuts of the network graph. While such methods exist, they all have certain limitations. This study proposes a new method for finding all cuts of a directed graph of arbitrary dimension, which eliminates these limitations, describes the algorithm for this method, and provides theoretical justification. The concept of the method is based on constructing graph cuts (multicuts) in such a way that all cuts are identified, and can be done in a reasonable amount of time. Examples of engineering networks where this method can be used as a tool for making rational decisions in operating network objects include power grids, transportation networks, water supply and sewerage networks, as well as communication and telecommunications networks.