**Reliability polynomials for all terminal reliability networks**

by Michael Monagan

**Abstract:**
Routine for the all terminal reliability polynomial for a graph G with probability of edge failure p.

**Application Areas/Subjects: **
Combinatorics & Graph Theory

**Keywords:**
reliability polynomial,

`> `
**restart:**

** Introduction**

The main function in this file is the routine relpoly(G,p). It computes the reliability polynomial a(p) for G the so called ``all-terminal reliability network''. Such a network is modelled by a graph G with multiple edges and with a probability p of failure on each edge. The polynomial a(p) gives the probability that the network is spanned in the presence of edge failures, i.e. the probability that each node remains connected to each other node. We give several examples below.

The algorithm used in this routine is a heuristic which works quite well for sparse networks, and appears to be much much (100 times) faster than the algorithm used in the routine networks[spanpoly] in the Maple library.

`> `

** Reliability polynomials **

The call relpoly(G,p) computes the reliability polynomial a(p) from the Graph G on N vertices. The input graph G should be input as a list of N polynomials in the vertices X[i], i=1..N, where the c = coeff(G[i],X[j]) gives the multiplicity of the edges from vertex i to j.

The input p is the edge probability and N is the number of vertices.

`> `
**relpoly := proc(G::list(polynom(nonnegint)),p) local n;**

n := nops(G);

reliability(G,p,n)

end:

`> `
**reliability := proc(G,p,n) local c,d,k,u,v,w,t,H;**

# Choose first vertex of minimum degree

d := n;

for k to nops(G) while d > 0 do

if G[k] <> infinity then

c := nops(indets(G[k]));

if c < d then d := c; u := k fi

fi;

od;

if d = 0 then if n = 1 then RETURN(1) else RETURN(0) fi fi;

v := op(1,op(1,indets(G[u]))); c := coeff(G[u],X[v],1);

if d = 1 then # Isolated node contraction

H := subsop( u=infinity, v=G[v]-c*X[u], G );

RETURN( expand( (1-(1-p)^c) * reliability(H,p,n-1) ) )

fi;

# Delete the edge of multiplicity c between vertices u & v

# (All edges between u and v have failed with probability (1-p)^c)

H := subsop( u=G[u]-c*X[v], v=G[v]-c*X[u], G );

t := (1-p)^c * reliability(H,p,n);

# Contract vertices u & v (at least one edge has not failed)

H := subsop( u=infinity, v=H[u]+H[v], subs(X[u]=X[v],H) );

t := expand( (1-(1-p)^c) * reliability(H,p,n-1) + t );

# Now remember this computation

reliability(G,p,n) := t;

end:

This is a utility routine to insert the edge u v into the graph G.

G should be initialized to vector (array) of N zeroes.

The third argument m specifies the multiplicity of the edge

**insert := proc(G,u,v,m)**

if nargs = 3 then insert(G,u,v,1) else

G[u] := G[u]+m*X[v];

G[v] := G[v]+m*X[u];

NULL

fi

end:

Example 1: computing the reliability polynomials for cliques

relpoly_clique(N,p); computes the reliability polynomial for a clique on N vertices with edge failure probability p

`> `
**relpoly_clique := proc(N,p) local G,i,j;**

G := array([0$N]);

for i to N-1 do for j from i+1 to N do insert(G,i,j) od od;

G := convert(G,list):

relpoly(G,p);

end:

`> `
**for i from 1 to 6 do**

printf(` Clique on %d vertices is\n`,i);

relpoly_clique(i,p);

od;

` Clique on 1 vertices is`

` Clique on 2 vertices is`

` Clique on 3 vertices is`

` Clique on 4 vertices is`

` Clique on 5 vertices is`

` Clique on 6 vertices is`

Example 2: reliability polynomials for simple loops

relpoly_loop(N,p); computes the reliability polynomial for

a simply cycle on N vertices with edge failure probability p

`> `
**relpoly_loop := proc(N,p) local G,i;**

G := array([0$N]);

for i to N-1 do insert(G,i,i+1) od;

insert(G,N,1);

G := convert(G,list):

relpoly(G,p);

end:

`> `
**for i from 1 to 6 do**

printf( ` Loop of %d vertices\n`, i );

relpoly_clique(i,p);

od;

` Loop of 1 vertices`

` Loop of 2 vertices`

` Loop of 3 vertices`

` Loop of 4 vertices`

` Loop of 5 vertices`

` Loop of 6 vertices`

Example 3: reliability polynomial for the Red Arpanet network

`> `
**relpoly_RedArpanet := proc(p) local N,G;**

N := 20;

G := array([0$N]):

insert(G,1,2):

insert(G,1,3):

insert(G,2,3):

insert(G,2,4):

insert(G,3,5):

insert(G,4,5):

insert(G,4,6):

insert(G,6,7):

insert(G,5,7):

insert(G,1,8):

insert(G,8,9):

insert(G,9,10):

insert(G,9,11):

insert(G,10,11):

insert(G,7,10):

insert(G,6,11):

insert(G,8,12):

insert(G,10,15):

insert(G,11,20):

insert(G,12,13):

insert(G,13,14):

insert(G,14,15):

insert(G,13,15):

insert(G,14,18):

insert(G,12,16):

insert(G,15,17):

insert(G,16,17):

insert(G,16,18):

insert(G,17,19):

insert(G,18,19):

insert(G,18,20):

insert(G,19,20):

G := convert(G,list);

relpoly(G,p)

end:

`> `
**relpoly_RedArpanet(p);**

`> `