Revision history [back]
 | 1 | initial version |
As I understand, an equivalent definition of a spanning elementary subgraph is that degrees of its vertices equal 1 or 2. Here is a generator of such graphs from a given set of edges:
def constructSES(E,H=Graph(),i=0):
if i == len(E):
yield H
return
yield from constructSES(E,H,i+1)
e = E[i]
if ((not H.has_vertex(e[0])) or H.degree(e[0])<2) and ((not H.has_vertex(e[1])) or H.degree(e[1])<2):
H.add_edge(e)
yield from constructSES(E,H,i+1)
H.delete_edge(e)
Correspondingly, we can get a list all spanning elementary subgraphs of $G$ on 6 vertices as follows:
SES = [H for H in constructSES(G.edges()) if H.order()==6]
It turns out that for a given graph there 40 such subgraphs on 6 vertices.
| | 2 | No.2 Revision |
As I understand, an equivalent definition of a spanning elementary subgraph is that degrees of its vertices equal 1 or 2. Here is a generator of such graphs from a given set of edges:
def constructSES(E,H=Graph(),i=0):
if i == len(E):
yield H
return
yield from constructSES(E,H,i+1)
e = E[i]
if ((not H.has_vertex(e[0])) (not H.has_vertex(e[0]) or H.degree(e[0])<2) and ((not H.has_vertex(e[1])) (not H.has_vertex(e[1]) or H.degree(e[1])<2):
H.add_edge(e)
yield from constructSES(E,H,i+1)
H.delete_edge(e)
Correspondingly, we can get a list all spanning elementary subgraphs of $G$ on 6 vertices as follows:
SES = [H for H in constructSES(G.edges()) if H.order()==6]
It turns out that for a given graph there 40 are such subgraphs on 6 vertices.
| | 3 | No.3 Revision |
As I understand, an equivalent definition of a spanning elementary subgraph UPD, Solution is that degrees of its vertices equal 1 or 2.
modified with respect to the edited question.
Here is a generator of such graphs from a given set of edges:
def constructSES(E,H=Graph(),i=0):
constructSES(G):
C = [tuple(c) for c in G.cycle_basis(output='edge')]
for S in Subsets(C):
T = set()
for c in S:
for e in c:
if e in T:
T.remove(e)
else:
T.add(e)
H = Graph()
H.add_edges(T)
yield from add_edges_SES(list(set(G.edges())-T),H)
def add_edges_SES(E,H,i=0):
if i == len(E):
yield H
H.copy()
return
yield from constructSES(E,H,i+1)
add_edges_SES(E,H,i+1)
e = E[i]
if (not H.has_vertex(e[0]) or H.degree(e[0])<2) H.has_vertex(e[0])) and (not H.has_vertex(e[1]) or H.degree(e[1])<2):
H.has_vertex(e[1])):
H.add_edge(e)
yield from constructSES(E,H,i+1)
H.delete_edge(e)
add_edges_SES(E,H,i+1)
H.delete_vertices(e[:2])
Correspondingly, we can get a list all spanning elementary subgraphs of $G$ on 6 vertices as follows:
SES = [H for H in constructSES(G.edges()) constructSES(G) if H.order()==6]
It turns out that for a given graph there 40 are 6 such subgraphs on 6 vertices.
| | 4 | No.4 Revision |
UPD, Solution is modified with respect to the edited question.
Here is a generator of such graphs from a given set of edges:
def constructSES(G):
C = [tuple(c) for c in G.cycle_basis(output='edge')]
for S in Subsets(C):
T = set()
for c in S:
for e in c:
if e in T:
T.remove(e)
else:
T.add(e)
H = Graph()
H.add_edges(T)
yield from add_edges_SES(list(set(G.edges())-T),H)
def add_edges_SES(E,H,i=0):
if i == len(E):
yield H.copy()
return
yield from add_edges_SES(E,H,i+1)
e = E[i]
if (not H.has_vertex(e[0])) and (not H.has_vertex(e[1])):
H.add_edge(e)
yield from add_edges_SES(E,H,i+1)
H.delete_vertices(e[:2])
def constructSES(G):
C = [frozenset(c) for c in G.cycle_basis(output='edge')]
for S in Subsets(C):
T = set()
for c in S:
T = T.symmetric_difference(c)
H = Graph()
H.add_edges(T)
yield from add_edges_SES(list(set(G.edges())-T),H)
Correspondingly, we can get a list all spanning elementary subgraphs of $G$ on 6 vertices as follows:
SES = [H for H in constructSES(G) if H.order()==6]
It turns out that for a given graph there are 6 such subgraphs on 6 vertices.
| | 5 | No.5 Revision |
UPD, Solution is modified with respect to the edited question.
Here is a generator of such graphs from a given set of edges:
def add_edges_SES(E,H,i=0):
if i == len(E):
yield H.copy()
return
yield from add_edges_SES(E,H,i+1)
e = E[i]
if (not H.has_vertex(e[0])) and (not H.has_vertex(e[1])):
H.add_edge(e)
yield from add_edges_SES(E,H,i+1)
H.delete_vertices(e[:2])
def constructSES(G):
C = [frozenset(c) for c in G.cycle_basis(output='edge')]
for S in Subsets(C):
T = set()
for c in S:
T = T.symmetric_difference(c)
H = Graph()
H.add_edges(T)
if all( H.degree(v) == 2 for v in H.vertices() ): # only simple cycles allowed
yield from add_edges_SES(list(set(G.edges())-T),H)
Correspondingly, we can get a list all spanning elementary subgraphs of $G$ on 6 vertices as follows:
SES = [H for H in constructSES(G) if H.order()==6]
It turns out that for a given graph there are 6 such subgraphs on 6 vertices.
| | 6 | No.6 Revision |
UPD, Solution is modified with respect to the edited question.
Here is a generator of such graphs from a given set of edges:
def add_edges_SES(E,H,i=0):
if i == len(E):
yield H.copy()
return
yield from add_edges_SES(E,H,i+1)
e = E[i]
if (not H.has_vertex(e[0])) and (not H.has_vertex(e[1])):
H.add_edge(e)
yield from add_edges_SES(E,H,i+1)
H.delete_vertices(e[:2])
def constructSES(G):
C = [frozenset(c) [frozenset(tuple(sorted(e[:2])) for e in c) for c in G.cycle_basis(output='edge')]
for S in Subsets(C):
T = set()
for c in S:
T = T.symmetric_difference(c)
H = Graph()
H.add_edges(T)
if all( H.degree(v) == 2 for v in H.vertices() ): # only simple cycles allowed
yield from add_edges_SES(list(set(G.edges())-T),H)
Correspondingly, we can get a list all spanning elementary subgraphs of $G$ on 6 vertices as follows:
SES = [H for H in constructSES(G) if H.order()==6]
It turns out that for a given graph there are 6 such subgraphs on 6 vertices.
