SM-3g-IndependencePolynomials

4145 days ago by nhanbaoho

In our last exemplary worksheet we will implement an algorithm for computing the independence polynomial of a given graph $G$. The first method we need is a simple one which determines whether or not an input graph is complete:
def is_complete(G): return G.num_edges() == binomial(G.num_verts(),2) print is_complete(graphs.CompleteGraph(5)) print is_complete(graphs.CycleGraph(5)) 
       
True
False
True
False
Just so we have it on hand, let's write a simple method to compute the product of an input list of polynomials (or other multipliable terms):
def prod(L): if len(L) == 1: return L[0] else: return L[0]*prod(L[1:len(L)]) prod([1,2,3,4]) 
       
24
24
All right, on to the main event. The following method computes the independence polynomial $I(G;x)$ of a given graph $G$ by using a simple "vertex-deletion" algorithm.
def ind_poly(G): if is_complete(G): return(G.order()*x+1) else: if G.is_connected(): v = G.vertices()[0] nbhd = G.neighbors(v) comp_nbhd = (Set(G.vertices()).difference(Set(union(nbhd,[v])))).list() i1 = ind_poly(G.subgraph(G.vertices()[1:])) if len(comp_nbhd) == 0: i2 = 1 else: i2 = ind_poly(G.subgraph(comp_nbhd)) return i1 + x*i2 else: comps = G.connected_components_subgraphs() return prod([ind_poly(comps[i]) for i in [0..len(comps)-1]]) G = graphs.PetersenGraph() show(G) ind_poly(G).expand() 
       

5*x^4 + 30*x^3 + 30*x^2 + 10*x + 1

5*x^4 + 30*x^3 + 30*x^2 + 10*x + 1
Let's try it out on a random tree:
H=Graph({0:1}) 
       
G = graphs.RandomBarabasiAlbert(25,1) show(G)