Дана решетка. Выделены два терминала: в нижнем левом углу и верхнем правом углу. Каждому ребру сопоставлена его надежность (вероятность связности)
.
Вот мне интересно, задача вычисления надежности решетки (вероятности связности терминалов) NP-трудная? То есть может кто видел ссылку на конкретную работу..Я не видела.
Мне кажется, что да. Во многих статьях, при анализе алгоритмов вычисления надежности графа, часто в качестве тестовых графов используют решетки, типа как нехорошие примеры.. Заранее большое спасибо за любую помощь
