Структурно-сложные системы с пороговой живучестью

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