О надежности последовательно-параллельных сетей в решетчатых графах

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