Универсальная графовая модель циклических сетей и их надежность

В данной статье теория доминирования распространяется на циклические монотонные графы, являющиеся универсальной графовой моделью для анализа надежности структурно сложных систем. В частности, получена формула расчета надежности произвольного монотонного графа, сводящая системный уровень анализа надежности к элементному уровню. В качестве следствия доказано, что для любого фиксированного целого $k$; задача определения надежности монотонных графов степени $k$ разрешима за время, полиномиально зависящее от размерности графов и числа их ациклических монотонных подграфов. В то же время показано, что задача определения надежности является $NP$-трудной даже в классе ациклических $dc$-тривиальных монотонных графов степени 2, в которых число минимальных ациклических подграфов пропорционально числу вершин графов.