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

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

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