СТРУКТУРНО-СЛОЖНЫЕ СИСТЕМЫ С ПОРОГОВОЙ ЖИВУЧЕСТЬЮ

Abstract

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