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
Let's try it out on a random tree:
H=Graph({0:1})
|
|
G = graphs.RandomBarabasiAlbert(25,1)
show(G)
|
|