Considering a network of $n$ IT centers $1,...,n$ we can connect by lines which heve different characteristics. Among these charateristics, we take an interrest in the reliability of a line. Thus, let be the error rate $p_{ij}$ which represents the probability for a message channeled by a line tio be corrupted. We admit that the probability are independant. Furthermore, the mise en place of a line entails noteworthy costs that we admit to be be identic for each lines.

The network administrator wants to pass a message toward every center. In order to do that he has to select with the least cost some lines from which the message would go from center to center. All lines and centers form a sub-network. The administrator which that this sub-network would be of maximal realiability.

  1. After having characterzied the type of the graph you are searching for, and defined the reliability of a sub-network, formalized clearly the problem

  2. Show that affecting to each edge the value $\log (1-p_{ij})$, we get a classical problem of graph theory (please do not answer this question wich I wrote because I tought it could help understand the $1^{st}$one)

  • I have said that it was about the algorithm of Sollin. Indeed, we are looking for a spanning tree which will allow messages to transit towards every centers. It has to be with minimal values because we are searching to minimze the error rate $p_{ij}$ .

original graph

After applying Sollin's algorithm we may have:

The graph after applyong Sollin's algorithm

  • The reliability of a line is the probability that every center of a sub-network get the message. The reliable rate is $1-p_{ij}$ between two edges. Here it may be $r=(1-p_{12})(1-p_{25})(1-p_{35})(1-p_{45})$

  • I would "clearly formalize this problem" saying that: We are looking for the spanning tree with the most reliable rate. We want to maximize $\prod (1- p_{ij})$ from a chosen vertice toward the others with Sollin's Algorithm.

But it seems to me that this is not enough. I do not show clearly mathemiatcally the potential cases I may face if I have odd trees... Furthermore, I don't know how the second question help me concluding with this first one...

How can I formalize according to the graph theory and mathematically such a problem? Don't hesitate to give me only hints if you think I can found it on my own.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.