Code to find separating set in SageMath of a given Graph

permutation

asked 5 years ago

Captcha
65 ●6 ●8 ●16

updated 3 years ago

slelievre
17789 ●22 ●163 ●352 http://carva.org/samue...

Given a Graph $G$ how can I find the separating set of the Graph?

Suppose I am given this graph

G = Graph({1: [2, 3, 4, 5],
           2: [1, 3, 4, 5],
           3: [1, 2, 4, 5],
           4: [1, 2, 3],
           5: [1, 2, 3]})

I want to find the set of vertices whose removal disconnects the graph.

I found that the vertex connectivity of $G$ is 2.

Looking at the graph, the smallest set of vertices whose removal disconnects the graph is $(1, 2, 3)$ .

But how to find it using a code in SageMath?

add a comment

2 Answers

Sort by » oldest newest most voted

answered 5 years ago

dazedANDconfused
908 ●3 ●15 ●29

Try this code:

from sage.graphs.connectivity import vertex_connectivity
G=Graph({1:[2,3,4,5],2:[1,3,4,5],3:[1,2,4,5],4:[1,2,3],5:[1,2,3]})
vertex_connectivity(G,value_only=False)

The result, running in a SageCell Server is

(3, [1, 2, 3])

Which says the vertex connectivity is 3 and the vertices 1,2,3 are such a set.

The documentation for vertex_connectivity() is here.

link

Comments

Thanks a lot sir. Can you kindly tell if there is any code which can find all the minimal separating sets of a given graph? How to write such a code

Captcha ( 5 years ago )

I don't see anything in the documentation that would provide all minimal separating sets of a graph. Given that circulants would have a lot of vertex separating sets, I don't see any way around brute force checking whether the removal of k vertices (where k is the vertex connectivity) over all subsets of k vertices results in a disconnected graph. If so add to the list.

dazedANDconfused ( 5 years ago )

Okay Thank you so much

Captcha ( 5 years ago )

add a comment

answered 3 years ago

licheng
311 ●6 ●25 ●43

updated 3 years ago

slelievre
17789 ●22 ●163 ●352 http://carva.org/samue...

The networkx package can be used to find all minimum separating sets.

sage: import networkx as nx
sage: G = Graph({1: [2, 3, 4, 5],
....:            2: [1, 3, 4, 5],
....:            3: [1, 2, 4, 5],
....:            4: [1, 2, 3],
....:            5: [1, 2, 3]})
sage: G1 = G.networkx_graph()  
sage: cutsets = list(nx.all_node_cuts(G1))
sage: cutsets
[{1, 2, 3}]

So G has only one minimum separated set.

See the documentation:

networkx documentation: all_node_cuts

link

add a comment

Your Answer

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

Add Answer

Code to find separating set in SageMath of a given Graph

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Code to find separating set in SageMath of a given Graph savecancel

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Code to find separating set in SageMath of a given Graph