УНИВЕРСАЛЬНАЯ ГРАФОВАЯ МОДЕЛЬ ЦИКЛИЧЕСКИХ СЕТЕЙ И ИХ НАДЕЖНОСТЬ

Abstract

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