Processing math: 100%
Ask Your Question
1

Spanning elementary subgraphs on a given number of vertices

asked 3 years ago

rewi gravatar image

updated 3 years ago

Max Alekseyev gravatar image

Consider the following definition:

A subgraph H of a graph G is called an elementary subgraph if each component of H is either an edge or a simple cycle of length at least 3. A spanning elementary subgraph is a subgraph having all components either edge (edge is a path on two vertices) or simple cycles.

Now my problem is: Consider the following code:

G = graphs.EmptyGraph()
G.add_edges([(1, 2), (2, 3), (3, 4), (4, 5), (5, 2), (6, 5), (6, 7)])
G.show()

Can we have a Sage code that gives all possible spanning subgraphs on 6 vertices of the above graph?

Actually I am trying to find the all possible spanning elementary subgraphs on 6 vertices of the above graph. By 6 vertices, I mean the subgraphs of order 6 of the original graph.

Preview: (hide)

Comments

Should subgraphs be induced?

Max Alekseyev gravatar imageMax Alekseyev ( 3 years ago )

yes, you are correct

rewi gravatar imagerewi ( 3 years ago )

No no, ..there are spanning elementary subgraphs on 6 vertices. for example, (1,2),(3,4),(5,6) is a spanning elementary subgraphs on 6 vertices. there are many more. another is (1,2),(3,4),(6,7). All these spanning elementary subgraphs contains only edge components. There may be cycle components also. for example (2,3,4,5),(6,7) is a spanning elementary subgraph on 6 vertices. I am trying to compute all possible spanning elementary subgraphs on 6 vertices. Is it clear now? if there is any problem, please let me know.

rewi gravatar imagerewi ( 3 years ago )

These subgraphs are not induced.

Max Alekseyev gravatar imageMax Alekseyev ( 3 years ago )

2 Answers

Sort by » oldest newest most voted
3

answered 3 years ago

Max Alekseyev gravatar image

updated 3 years ago

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(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.

Preview: (hide)
link

Comments

The code creates a list SES of such subgraphs. Then you can do whatever you want with it. E.g., to show them all run:

for H in SES:
    H.show()

or to print their edges run:

for H in SES:
    print(H.edges())
Max Alekseyev gravatar imageMax Alekseyev ( 3 years ago )

Actually I am trying to get an answer of the type given in https://ask.sagemath.org/question/435...

rewi gravatar imagerewi ( 3 years ago )

Actually my question is the following: Find all possible spanning elementary subgraphs on 12 vertices of the following graph.

G=graphs.EmptyGraph()

G.add_edges([(1,2),(2,3),(3,4),(4,5),(6,7),(6,5),(1,7),(3,6),(6,8),(8,11),(8,9),(9,10),(10,11),(11,12),(12,8),(12,13)])

G.show()

rewi gravatar imagerewi ( 3 years ago )

For example A=(1,2),(7,6),(3,4),(12,13),(8,9),(10,11) and B=(1,2,3,6,7),(8,11,12),(4,5),(9,10) are two spanning elementary subgraphs on 12 vertices of the given graph G. Here A consists only of edges while B contains both edge and cycle components. There are other spanning elementary subgraphs on 12 vertices of the graph G. How to use sagemath to calculate all those spanning elementary subgraphs on 12 vertices of the graph G? Am I clear now?

rewi gravatar imagerewi ( 3 years ago )

What's wrong with the posted solution?

Max Alekseyev gravatar imageMax Alekseyev ( 3 years ago )
1

answered 3 years ago

updated 3 years ago

This question has already been (nicely) answered https://ask.sagemath.org/question/435...

I copy here my answer (with small changes to return graphs).

def elementary_subgraphs(G, nmin=0):
    r"""
    Iterator over the elementary subgraphs of `G`.

    A subgraph `H` of a graph `G` is *elementary* if each of its connected
    components is either an edge or a cycle.

    INPUT:

    - ``G`` -- a Graph

    - ``nmin`` -- integer (default: ``0``); lower bound on the number of
      vertices involved in the elementary subgraphs of any returned
      solution. When set to ``G.order()``, the subgraphs must be spanning.
    """
    G._scream_if_not_simple()

    def rec(H, low):
        if not H.size():
            yield Graph()
            return
        if H.order() < low:
            # no solution
            return

        # We select an edge e = (u, v) of H and remove it
        u, v = next(H.edge_iterator(labels=False))
        H.delete_edge((u, v))

        # Case 1: return solutions without e
        for g in rec(H, low):
            if g.order() >= low:
                yield g

        # Case 2: select e as an isolated edge
        I = H.edges_incident([u, v])
        H.delete_vertices([u, v])
        for g in rec(H, low - 2):
            if g.order() + 2 >= low:
                g.add_edge(u, v)
                yield g
        H.add_vertices([u, v])
        H.add_edges(I)

        # Case 3: select e as part of a cycle
        for P in H.all_paths(u, v):
            K = H.copy()
            K.delete_vertices(P)
            nP = len(P)
            for g in rec(K, low - nP):
                if g.order() + nP >= low:
                    g.add_cycle(P)
                    yield g

        # Finally restore edge e
        H.add_edge(u, v)

    yield from rec(G.copy(), nmin)

We can use it like:

sage: G = Graph([(1,2),(2,3),(3,4),(4,5),(5,2),(6,5),(6,7)])
sage: ES = [H for H in elementary_subgraphs(G, nmin=6)]
sage: len(ES)
6
Preview: (hide)
link

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 3 years ago

Seen: 649 times

Last updated: Feb 10 '22