Solutions for Questions 1, 2, 3.

CSE 591 Assignment One

  1. Let G=(V,E) be an undirected graph, and consider the all-terminal operation on G. Suppose that e={x,y} is an edge of G, and that z is a vertex different from x and y. Form a graph G' by removing the edge e and adding the edges e'={x,z} and e''={y,z}, so that p_e = p_{e'} = p_{e''}.

    Establish a relationship between the all-terminal reliability of G and that of G'.

    Solution: Consider the possible states of G-e. Partition these states into classes as follows:

    Let Pr[X] denote the probability of being in a state of type X. Now compute the reliability of G as follows. If the state of G-e is type I, edge e can operate or fail; if type IIb or type IIc, edge e must operate; and if any other type, there is no way for e to make the state operational. So the reliability of G is Pr[I] + p_e (Pr[IIb] + Pr[IIc]).

    Now compute the reliability of G'. If type I, e' and e'' can both either operate or fail. If type IIa, either e' or e'' or both must operate. If type IIb, e'' must operate, and e' can operate or fail. If type IIc, e' must operate, and e'' can operate or fail. If type III, both e' and e'' must operate. If type IV, there is no way for e' and e'' to connect the state. So the reliability of G' is Pr[I] + (2p_e - p_e*p*e) Pr[IIa] + p_e(Pr[IIb] + Pr[IIc]) + p_e*p_e*Pr[III].

    The difference between the reliability of G' and that of G is (2p_e - p_e*p*e) Pr[IIa] + p_e*p_e*Pr[III]. Since probabilities are always nonnegative, this difference is nonnegative, and hence G' IS AT LEAST AS RELIABLE AS G.

    In fact, equality occurs only when p_e = 0, or when Pr[IIa] = Pr[III] = 0. (Exercise: does the latter ever occur?)

  2. Let G=(V,E) be an undirected graph, and let s and t be target vertices in a two-terminal operation on G. Let v be a vertex different from s and t, and let I be the set of edges incident with v. Form a new graph G' as follows: Add two new vertices v' and v''. Now for each edge in I, replace v in that edge either by v' or v''. Then delete vertex v. In each such substitution, the edge operation probability does not change.

    Establish a relationship between the two-terminal reliability of G and that of G'.

    Solution: Consider the states of G-v (i.e., G with the vertex v and all of its incident edges deleted). Call a state type I if there is an operating s,t-path. Call it type II if there is no operating s,t path BUT there is an operating s,w-path and an operating x,t-path in G-e, and there are edges {v,w} and {v,x} in G. Call all others type III.

    Now if the state is type I, the state is operational whether or not any edges incident with v operate, so the transformation does not change the state of operation here. Similarly, if the state is type III, no matter which other edges operate involving v (or v' and v''), there is no way to connect s and t. Again the state of operation remains unchanged.

    So the only potentially affected states are the type II ones. Fix a particular type II state S, and consider the states of the edges in G that are incident to v. If these fail to connect the components involving s and t, then the corresponding edges in G' also fail to connect s and t. If these succeed in connecting s and t, they may nevertheless fail to do so in G', since it may happen that one operating edge goes to v' while the other goes to v''.

    We conclude that since every operating state of G' corresponds to an operating state of G having the same occurrence probability, and since the converse need not be true, that G IS AT LEAST AS RELIABLE AS G'. Equality holds whenever every s,t-path in G that passes through v has an edge of zero operation probability on it, or remains an s,t-path in G' with the replacement of v by v' or v''.

  3. Let G=(V,E) be an undirected graph. Suppose that {s,t} is a subset of K, K is a subset of K', and K' is a subset of V.

    Establish a relationship between the k-terminal reliability of G for target set K and the k-terminal reliability of G for target set K'.

    Solution: Consider a state of G. If G is operating for K', then there are paths of operating edges connecting every pair of vertices in K'. But K is a subset of K', and so every pair of vertices in K is also connected by a path of operating edges, and the state is operational for K. In general, connecting all pairs in K will not suffice to connect all pairs in K', so we conclude that the k-terminal reliability of G for K' IS NO LARGER THAN the k-terminal reliability of G for K.

    Equality occurs when every Steiner tree for K' containing no edge of zero probability is also a Steiner tree for K. (Example, take a star with center vertex c and leaf vertices {x,y,z}; then every Steiner tree for {x,y,z} contains c, and so the Steiner trees for {x,y,z} and {x,y,z,c} are the same.)

  4. Implement a basic complete state enumeration algorithm for k-terminal reliability; explain any decisions you made to improve efficiency, but DO GENERATE ALL STATES to test them for operation.

  5. Implement a factoring method for two-terminal reliability using series-parallel reductions. Discuss your implementation.
For the programming, choose any language you like. Do not spend a lot of time on bells and whistles -- your main task is to get a basic easy-to-use program that you can do some simple tests on.