IndPoly2

4136 days ago by pbahls

def is_complete(G): return G.num_edges() == binomial(G.num_verts(),2) def prod(L): if len(L) == 1: return L[0] else: return L[0]*prod(L[1:len(L)]) 
       
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
def ind_poly2(G): if is_complete(G): return(G.order()*x+1) else: if G.is_connected(): e = G.edges()[0] u = e[0] v = e[1] nbhd_u = G.neighbors(u) nbhd_v = G.neighbors(v) comp_nbhd = (Set(G.vertices()).difference(Set(union(nbhd_u,nbhd_v)))).list() i1 = ind_poly2(G.subgraph(edges = G.edges()[1:])) if len(comp_nbhd) == 0: i2 = 1 else: i2 = ind_poly2(G.subgraph(vertices = comp_nbhd)) return i1 - (x^2)*i2 else: comps = G.connected_components_subgraphs() return prod([ind_poly2(comps[i]) for i in [0..len(comps)-1]]) show(G) ind_poly2(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