ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 05 Aug 2019 20:53:23 -0500Code to find separating set in SageMath of a given Graphhttps://ask.sagemath.org/question/47381/code-to-find-separating-set-in-sagemath-of-a-given-graph/ 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.
Also on seeing the graph I find that the set of vertices whose removal disconnects the graph will be $(1,2,3)$
But how to find it using a code in SageMath?Sun, 04 Aug 2019 07:52:38 -0500https://ask.sagemath.org/question/47381/code-to-find-separating-set-in-sagemath-of-a-given-graph/Answer by dazedANDconfused for <p>Given a Graph $G$ how can I find the separating set of the Graph?</p>
<p>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]})</p>
<p>I want to find the set of vertices whose removal disconnects the graph.</p>
<p>I found that the vertex connectivity of $G$ is 2.</p>
<p>Also on seeing the graph I find that the set of vertices whose removal disconnects the graph will be $(1,2,3)$</p>
<p>But how to find it using a code in SageMath?</p>
https://ask.sagemath.org/question/47381/code-to-find-separating-set-in-sagemath-of-a-given-graph/?answer=47383#post-id-47383Try 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](https://sagecell.sagemath.org/) 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](http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/connectivity.html#sage.graphs.connectivity.vertex_connectivity). Sun, 04 Aug 2019 10:27:23 -0500https://ask.sagemath.org/question/47381/code-to-find-separating-set-in-sagemath-of-a-given-graph/?answer=47383#post-id-47383Comment by Captcha for <p>Try this code:</p>
<pre><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)
</code></pre>
<p>The result, running in a <a href="https://sagecell.sagemath.org/">SageCell Server</a> is </p>
<pre><code>(3, [1, 2, 3])
</code></pre>
<p>Which says the vertex connectivity is 3 and the vertices 1,2,3 are such a set.</p>
<p>The documentation for vertex_connectivity() is <a href="http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/connectivity.html#sage.graphs.connectivity.vertex_connectivity">here</a>. </p>
https://ask.sagemath.org/question/47381/code-to-find-separating-set-in-sagemath-of-a-given-graph/?comment=47402#post-id-47402Okay Thank you so muchMon, 05 Aug 2019 20:53:23 -0500https://ask.sagemath.org/question/47381/code-to-find-separating-set-in-sagemath-of-a-given-graph/?comment=47402#post-id-47402Comment by dazedANDconfused for <p>Try this code:</p>
<pre><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)
</code></pre>
<p>The result, running in a <a href="https://sagecell.sagemath.org/">SageCell Server</a> is </p>
<pre><code>(3, [1, 2, 3])
</code></pre>
<p>Which says the vertex connectivity is 3 and the vertices 1,2,3 are such a set.</p>
<p>The documentation for vertex_connectivity() is <a href="http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/connectivity.html#sage.graphs.connectivity.vertex_connectivity">here</a>. </p>
https://ask.sagemath.org/question/47381/code-to-find-separating-set-in-sagemath-of-a-given-graph/?comment=47396#post-id-47396I 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.Mon, 05 Aug 2019 09:52:55 -0500https://ask.sagemath.org/question/47381/code-to-find-separating-set-in-sagemath-of-a-given-graph/?comment=47396#post-id-47396Comment by Captcha for <p>Try this code:</p>
<pre><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)
</code></pre>
<p>The result, running in a <a href="https://sagecell.sagemath.org/">SageCell Server</a> is </p>
<pre><code>(3, [1, 2, 3])
</code></pre>
<p>Which says the vertex connectivity is 3 and the vertices 1,2,3 are such a set.</p>
<p>The documentation for vertex_connectivity() is <a href="http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/connectivity.html#sage.graphs.connectivity.vertex_connectivity">here</a>. </p>
https://ask.sagemath.org/question/47381/code-to-find-separating-set-in-sagemath-of-a-given-graph/?comment=47385#post-id-47385Thanks 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 codeMon, 05 Aug 2019 00:53:28 -0500https://ask.sagemath.org/question/47381/code-to-find-separating-set-in-sagemath-of-a-given-graph/?comment=47385#post-id-47385