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 + 1def 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