On complexity of reliable probabilistic networks (Q1841316)

Some non-oriented networks with \(m\) input poles and \(h\) output poles, i.e. the \((m,n)\)-poles networks, every edge of which belongs to one of the non-crossing classes \(K_1,\dots{}, K_l\) are considered. It is supposed that the every edge \(u\) of the classe \(K_i\), \(i\ni \{1,\dots{},l\}\) has a cost \(c(u)=c_i\), \(c_i>0\) and can be in a conducting state with the probability \(p(u)=p_i\) and in a non-conducting state with the probability \(q(u)=1-p(u)\) inspite of states of the other edges. Additionally it is supposed that every line connecting two vertex of the \( (m,h)\)-poles network \(S\) is considered as a conducting one if every edge of the line is in a conducting state. A complexity of the network is determined as a summary cost all of its edges. Some complexity estimates (including an asymptotic one for the \((1,1)\)-poles network) of a minimal cost network are obtained. Here it was taken into consideration that for any pair ''input-output'' the probability of existence of a conducting line between the input and the output is not less than a given number \(n\) \((0<n<1)\).