(Sage) from sage.graphs.connectivity import connected_components
def recurse(g):
if g.order() == 0:
return 1
comp = g.connected_components()
if len(comp[-1]) == 1:
return 0
elif len(comp) > 1:
prod = 1
for c in comp:
if prod == 0:
return 0
else:
prod = prod*recurse(g.subgraph(vertices=c))
return prod
min_degree_vertex = g.vertices()[0]
for v in g.vertices():
if g.degree(v) < g.degree(min_degree_vertex):
min_degree_vertex = v
to_remove_edge = g.edges_incident(min_degree_vertex)[0]
to_remove_vertices = [to_remove_edge[0], to_remove_edge[1]]
to_remove_vertices.extend(g.neighbors(to_remove_edge[0]))
to_remove_vertices.extend(g.neighbors(to_remove_edge[1]))
to_remove_vertices = list(set(to_remove_vertices))
without_neighborhoods = copy(g)
without_edge = copy(g)
without_neighborhoods.delete_vertices(to_remove_vertices)
without_edge.delete_edge(to_remove_edge)
return recurse(without_edge) - recurse(without_neighborhoods)
def a(n):
if n == 0:
return recurse(graphs.CompleteGraph(1))
else:
return recurse(graphs.CubeGraph(n))
|