Ask Your Question
2

How to find the spanning elementary subgraphs of a given graph

asked 2018-09-04 08:02:42 -0500

Kuldeep gravatar image

updated 2018-09-17 13:25:20 -0500

tmonteil 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 ( $K_{2}$ ) or a cycle of length at least $3$. A spanning elementary subgraph is a subgraph having all components either path(i.e. $K_{2}$) or cycles and verex set is same as those of $G$. for example consider the graph $C_{4}$ with $V(G)$={1,2,3,4}. then it has 3 spanning elementary subgraphs two edge components namely {12,34};{14,23} and the whole cycle itself.The cycle is named in anticlockwise direction. Now my problem is: Consider the following code:

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

Can we have a sage code that gives all possible spanning subgraphs of this graph.

edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
2

answered 2018-09-17 12:56:17 -0500

tmonteil gravatar image

updated 2018-09-17 13:05:04 -0500

There is a generic tool for solving such problems without having to think too much: Integer Linear Programming.

For each edge $uv$ of your graph, you define two binary variables (with values in {0, 1} ): one named $c(uv)$ telling that a cycle from you spanning configuration that is passing through the edge $uv$, and one names $e(uv)$ telling whether the edge the edge $uv$ is selected as an edge of the spanning configuration.

Then, you add the following constraint: for each vertex $v$, there is either exactly one edge adjacent to it that is selected to be an edge of the spanning configuration, or there are exactly two edges adjacent to it that are selected to be part of a cycle of the spanning configuration.

This constraints translates into the following linear equalities: $\forall v \in V(G), \sum_{uv \in E(G)} 2*e(uv) + c(uv) =1$ (E)

Hence, the set of solutions you want can be seen as the set of integer points of the polytope defined by the equation (E) together with the equations $0\leq e(uv)\leq1$ and $0\leq c(uv)\leq1$ for all edge $uv \in E(G)$.

The way to define this polytope in Sage is done by using the polyhedron method of the MixedIntegerLinearProgram class.

Here is the code of the function (some explanations will follow):

def spanning_elementary_subgraphs(G):
    p = MixedIntegerLinearProgram(solver='ppl')
    e = p.new_variable(binary=True)
    c = p.new_variable(binary=True)

    # those are useless constraints, only to control the order in which the variables are created, see discussion below
    for edge in G.edges(labels=False):
        p.add_constraint(e[edge] >= 0)
    for edge in G.edges(labels=False):
        p.add_constraint(c[edge] >= 0)

    for v in G.vertices():
        p.add_constraint(sum(2*e[edge] + c[edge] for edge in G.edges_incident(v, labels=False)) == 2)

    P = p.polyhedron(backend='normaliz')
    for i,L in enumerate(P.integral_points()):
        edges = []
        cycle_edges = []
        for j,edge in enumerate(G.edges(labels=False)):
            if L[j] == 1:
                edges.append(edge)
            if L[j+G.num_edges()] == 1:
                cycle_edges.append(edge)
        H = Graph(cycle_edges, format='list_of_edges')
        yield {'edges': edges, 'cycles': H.connected_components()}

This function returns an iterator over all solutions. At each iteration, you get a dictionary

Here is it working on your example:

sage: G = graphs.EmptyGraph()
sage: G.add_edges([(1,2),(2,3),(3,4),(4,5),(5,1),(6,5),(6,8),(8,9),(7,9),(7,6),(7,10),(10,11),(10,12),(11,12)])

sage: s = spanning_elementary_subgraphs(G)
sage: list(s)
[{'cycles': [[1, 2, 3, 4, 5], [6, 7, 8, 9], [10, 11, 12]], 'edges': []},
 {'cycles': [[1, 2, 3, 4, 5], [10, 11, 12]], 'edges': [(6, 8), (7, 9)]},
 {'cycles': [[1, 2, 3, 4, 5], [10, 11, 12]], 'edges': [(6, 7), (8, 9)]},
 {'cycles': [], 'edges': [(1, 2), (3, 4), (5, 6), (7, 10), (8, 9), (11, 12)]}]

So, you can see that there are exactly 4 possible spanning configurations.

Now, some more explanations about the code.

First, when we construct the polyhedron, we have to use the normaliz backend or the computation will be too slow. To be able to use it, you have to install the pynormaliz optional package, by typing from a terminal:

sage -i pynormaliz

Then, there is a total of $2*|E(G)|$ variables: for each edge $uv$, there is $e(uv)$ and $c(uv)$. Each variable will be an element of the basis of the space where the polyhedron lives.

The problem is that, in the current Sage user interface, there is no easy way to see order of the variables that are used to define that basis.

The variables are created on the fly when used for the first time. Since there is a loop over the vertices $v$ and then a loop over the edges $uv$ adjacent to the current vertex $v$ and then a constraint involving both $e(uv)$ and $c(uv)$, it is hard to guess the order of the basis.

Hence, we added some useless constraints in two flat loops in whch the edges appear in a simple-to-handle order.

Note that it trick has nothing to do with interesting algorithmics or mathematics, it is only an annoyance of the current Sage user interface and should be solved by Sage developers (a ticket will follow).

edit flag offensive delete link more
1

answered 2018-09-05 10:48:02 -0500

A perfect matching (if the graph has one) is a spanning elementary subgraph according your definition. You can get all the perfect matchings (only 1 in your graph) using

sage: list(G.perfect_matchings())
[[(7, 10), (1, 2), (11, 12), (3, 4), (5, 6), (8, 9)]]

Now if you want all spanning elementary subgraphs, you have to design a specific algorithm.

edit flag offensive delete link more

Comments

Thank you. I am trying. But I have not been able to find the algorithm .

Kuldeep gravatar imageKuldeep ( 2018-09-05 11:00:59 -0500 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-09-04 08:02:42 -0500

Seen: 79 times

Last updated: Sep 17