Снижение размерности задачи нахождения критических узлов сети

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

устойчивость электрических сетей, поиск критических узлов, графовые модели сетей