Connectivity related functions¶
This module implements the connectivity based functions for graphs and digraphs. The methods in this module are also available as part of GenericGraph, DiGraph or Graph classes as aliases, and these methods can be accessed through this module or as class methods. Here is what the module can do:
For both directed and undirected graphs:
is_connected() |
Test whether the (di)graph is connected. |
connected_components() |
Return the list of connected components |
connected_components_number() |
Return the number of connected components. |
connected_components_subgraphs() |
Return a list of connected components as graph objects. |
connected_component_containing_vertex() |
Return a list of the vertices connected to vertex. |
connected_components_sizes() |
Return the sizes of the connected components as a list. |
blocks_and_cut_vertices() |
Compute the blocks and cut vertices of the graph. |
blocks_and_cuts_tree() |
Compute the blocks-and-cuts tree of the graph. |
is_cut_edge() |
Return True if the input edge is a cut-edge or a bridge. |
is_cut_vertex() |
Return True if the input vertex is a cut-vertex. |
edge_connectivity() |
Return the edge connectivity of the graph. |
vertex_connectivity() |
Return the vertex connectivity of the graph. |
For DiGraph:
is_strongly_connected() |
Returns whether the current DiGraph is strongly connected. |
strongly_connected_components_digraph() |
Returns the digraph of the strongly connected components |
strongly_connected_components_subgraphs() |
Returns the strongly connected components as a list of subgraphs. |
strongly_connected_component_containing_vertex() |
Returns the strongly connected component containing a given vertex. |
strong_articulation_points() |
Return the strong articulation points of this digraph. |
For undirected graphs:
bridges() |
Returns a list of the bridges (or cut edges) of given undirected graph. |
Methods¶
-
sage.graphs.connectivity.
blocks_and_cut_vertices
¶ Computes the blocks and cut vertices of the graph.
In the case of a digraph, this computation is done on the underlying graph.
A cut vertex is one whose deletion increases the number of connected components. A block is a maximal induced subgraph which itself has no cut vertices. Two distinct blocks cannot overlap in more than a single cut vertex.
INPUT:
algorithm
– The algorithm to use in computing the blocksand cut vertices of
G
. The following algorithms are supported:
"Tarjan_Boost"
(default) – Tarjan’s algorithm (Boost implementation)."Tarjan_Sage"
– Tarjan’s algorithm (Sage implementation).
OUTPUT:
(B, C)
, whereB
is a list of blocks - each is a list of vertices and the blocks are the corresponding induced subgraphs - andC
is a list of cut vertices.ALGORITHM:
We implement the algorithm proposed by Tarjan in [Tarjan72]. The original version is recursive. We emulate the recursion using a stack.See also
EXAMPLES:
We construct a trivial example of a graph with one cut vertex:
sage: from sage.graphs.connectivity import blocks_and_cut_vertices sage: rings = graphs.CycleGraph(10) sage: rings.merge_vertices([0, 5]) sage: blocks_and_cut_vertices(rings) ([[0, 1, 4, 2, 3], [0, 6, 9, 7, 8]], [0]) sage: rings.blocks_and_cut_vertices() ([[0, 1, 4, 2, 3], [0, 6, 9, 7, 8]], [0]) sage: blocks_and_cut_vertices(rings, algorithm="Tarjan_Sage") ([[0, 1, 2, 3, 4], [0, 6, 7, 8, 9]], [0])
The Petersen graph is biconnected, hence has no cut vertices:
sage: blocks_and_cut_vertices(graphs.PetersenGraph()) ([[0, 1, 4, 5, 2, 6, 3, 7, 8, 9]], [])
Decomposing paths to pairs:
sage: g = graphs.PathGraph(4) + graphs.PathGraph(5) sage: blocks_and_cut_vertices(g) ([[2, 3], [1, 2], [0, 1], [7, 8], [6, 7], [5, 6], [4, 5]], [1, 2, 5, 6, 7])
A disconnected graph:
sage: g = Graph({1:{2:28, 3:10}, 2:{1:10, 3:16}, 4:{}, 5:{6:3, 7:10, 8:4}}) sage: blocks_and_cut_vertices(g) ([[1, 2, 3], [5, 6], [5, 7], [5, 8], [4]], [5])
-
sage.graphs.connectivity.
blocks_and_cuts_tree
¶ Returns the blocks-and-cuts tree of
self
.This new graph has two different kinds of vertices, some representing the blocks (type B) and some other the cut vertices of the graph
self
(type C).There is an edge between a vertex \(u\) of type B and a vertex \(v\) of type C if the cut-vertex corresponding to \(v\) is in the block corresponding to \(u\).
The resulting graph is a tree, with the additional characteristic property that the distance between two leaves is even. When
self
is not connected, the resulting graph is a forest.When
self
is biconnected, the tree is reduced to a single node of type \(B\).We referred to [HarPri] and [Gallai] for blocks and cuts tree.
EXAMPLES:
sage: from sage.graphs.connectivity import blocks_and_cuts_tree sage: T = blocks_and_cuts_tree(graphs.KrackhardtKiteGraph()); T Graph on 5 vertices sage: T.is_isomorphic(graphs.PathGraph(5)) True sage: from sage.graphs.connectivity import blocks_and_cuts_tree sage: T = graphs.KrackhardtKiteGraph().blocks_and_cuts_tree(); T Graph on 5 vertices
The distance between two leaves is even:
sage: T = blocks_and_cuts_tree(graphs.RandomTree(40)) sage: T.is_tree() True sage: leaves = [v for v in T if T.degree(v) == 1] sage: all(T.distance(u,v) % 2 == 0 for u in leaves for v in leaves) True
The tree of a biconnected graph has a single vertex, of type \(B\):
sage: T = blocks_and_cuts_tree(graphs.PetersenGraph()) sage: T.vertices() [('B', (0, 1, 4, 5, 2, 6, 3, 7, 8, 9))]
-
sage.graphs.connectivity.
bridges
¶ Returns a list of the bridges (or cut edges).
A bridge is an edge whose deletion disconnects the undirected graph. A disconnected graph has no bridge.
INPUT:
labels
– (default:True
) ifFalse
, each bridge is a tuple \((u, v)\) of vertices
EXAMPLES:
sage: from sage.graphs.connectivity import bridges sage: from sage.graphs.connectivity import is_connected sage: g = 2*graphs.PetersenGraph() sage: g.add_edge(1,10) sage: is_connected(g) True sage: bridges(g) [(1, 10, None)] sage: g.bridges() [(1, 10, None)]
-
sage.graphs.connectivity.
connected_component_containing_vertex
¶ Returns a list of the vertices connected to vertex.
INPUT:
G
(generic_graph) - the input graph.v
- the vertex to search for.
EXAMPLES:
sage: from sage.graphs.connectivity import connected_component_containing_vertex sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: connected_component_containing_vertex(G,0) [0, 1, 2, 3] sage: G.connected_component_containing_vertex(0) [0, 1, 2, 3] sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: connected_component_containing_vertex(D,0) [0, 1, 2, 3]
-
sage.graphs.connectivity.
connected_components
¶ Returns the list of connected components.
Returns a list of lists of vertices, each list representing a connected component. The list is ordered from largest to smallest component.
INPUT:
G
(generic_graph) - the input graph.
EXAMPLES:
sage: from sage.graphs.connectivity import connected_components sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: connected_components(G) [[0, 1, 2, 3], [4, 5, 6]] sage: G.connected_components() [[0, 1, 2, 3], [4, 5, 6]] sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: connected_components(D) [[0, 1, 2, 3], [4, 5, 6]]
-
sage.graphs.connectivity.
connected_components_number
¶ Returns the number of connected components.
INPUT:
G
(generic_graph) - the input graph.
EXAMPLES:
sage: from sage.graphs.connectivity import connected_components_number sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: connected_components_number(G) 2 sage: G.connected_components_number() 2 sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: connected_components_number(D) 2
-
sage.graphs.connectivity.
connected_components_sizes
¶ Return the sizes of the connected components as a list.
The list is sorted from largest to lower values.
EXAMPLES:
sage: from sage.graphs.connectivity import connected_components_sizes sage: for x in graphs(3): print(connected_components_sizes(x)) [1, 1, 1] [2, 1] [3] [3] sage: for x in graphs(3): print(x.connected_components_sizes()) [1, 1, 1] [2, 1] [3] [3]
-
sage.graphs.connectivity.
connected_components_subgraphs
¶ Returns a list of connected components as graph objects.
EXAMPLES:
sage: from sage.graphs.connectivity import connected_components_subgraphs sage: G = Graph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: L = connected_components_subgraphs(G) sage: graphs_list.show_graphs(L) sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } ) sage: L = connected_components_subgraphs(D) sage: graphs_list.show_graphs(L) sage: L = D.connected_components_subgraphs() sage: graphs_list.show_graphs(L)
-
sage.graphs.connectivity.
edge_connectivity
¶ Returns the edge connectivity of the graph.
For more information, see the Wikipedia article on connectivity.
Note
When the graph is a directed graph, this method actually computes the strong connectivity, (i.e. a directed graph is strongly \(k\)-connected if there are \(k\) disjoint paths between any two vertices \(u, v\)). If you do not want to consider strong connectivity, the best is probably to convert your
DiGraph
object to aGraph
object, and compute the connectivity of this other graph.INPUT:
G
(generic_graph) - the input graph.value_only
– boolean (default:True
)- When set to
True
(default), only the value is returned. - When set to
False
, both the value and a minimum edge cut are returned.
- When set to
implementation
– selects an implementation:- When set to
None
(default): selects the best implementation available. - When set to
"boost"
, we use the Boost graph library (which is much more efficient). It is not available whenedge_labels=True
, and it is unreliable for directed graphs (see trac ticket #18753). - When set to
"Sage"
, we use Sage’s implementation.
- When set to
use_edge_labels
– boolean (default:False
)- When set to
True
, computes a weighted minimum cut where each edge has a weight defined by its label. (If an edge has no label, \(1\) is assumed.). Impliesboost
=False
. - When set to
False
, each edge has weight \(1\).
- When set to
vertices
– boolean (default:False
)- When set to
True
, also returns the two sets of vertices that are disconnected by the cut. Impliesvalue_only=False
.
- When set to
solver
– (default:None
) Specify a Linear Program (LP) solver to be used (ignored ifimplementation='boost'
). If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet.
EXAMPLES:
A basic application on the PappusGraph:
sage: from sage.graphs.connectivity import edge_connectivity sage: g = graphs.PappusGraph() sage: edge_connectivity(g) 3 sage: g.edge_connectivity() 3
The edge connectivity of a complete graph ( and of a random graph ) is its minimum degree, and one of the two parts of the bipartition is reduced to only one vertex. The cutedges isomorphic to a Star graph:
sage: g = graphs.CompleteGraph(5) sage: [ value, edges, [ setA, setB ]] = edge_connectivity(g,vertices=True) sage: value 4 sage: len(setA) == 1 or len(setB) == 1 True sage: cut = Graph() sage: cut.add_edges(edges) sage: cut.is_isomorphic(graphs.StarGraph(4)) True
Even if obviously in any graph we know that the edge connectivity is less than the minimum degree of the graph:
sage: g = graphs.RandomGNP(10,.3) sage: min(g.degree()) >= edge_connectivity(g) True
If we build a tree then assign to its edges a random value, the minimum cut will be the edge with minimum value:
sage: g = graphs.RandomGNP(15,.5) sage: tree = Graph() sage: tree.add_edges(g.min_spanning_tree()) sage: for u,v in tree.edge_iterator(labels=None): ....: tree.set_edge_label(u,v,random()) sage: minimum = min([l for u,v,l in tree.edge_iterator()]) sage: [value, [(u,v,l)]] = edge_connectivity(tree, value_only=False, use_edge_labels=True) sage: l == minimum True
When
value_only = True
andimplementation="sage"
, this function is optimized for small connectivity values and does not need to build a linear program.It is the case for graphs which are not connected
sage: g = 2 * graphs.PetersenGraph() sage: edge_connectivity(g, implementation="sage") 0.0
For directed graphs, the strong connectivity is tested through the dedicated function
sage: g = digraphs.ButterflyGraph(3) sage: edge_connectivity(g, implementation="sage") 0.0
We check that the result with Boost is the same as the result without Boost
sage: g = graphs.RandomGNP(15,.3) sage: edge_connectivity(g) == edge_connectivity(g, implementation="sage") True
Boost interface also works with directed graphs
sage: edge_connectivity(digraphs.Circuit(10), implementation = "boost", vertices = True) [1, [(0, 1)], [{0}, {1, 2, 3, 4, 5, 6, 7, 8, 9}]]
However, the Boost algorithm is not reliable if the input is directed (see trac ticket #18753):
sage: g = digraphs.Path(3) sage: edge_connectivity(g) 0.0 sage: edge_connectivity(g, implementation="boost") 1 sage: g.add_edge(1,0) sage: edge_connectivity(g) 0.0 sage: edge_connectivity(g, implementation="boost") 0
-
sage.graphs.connectivity.
is_connected
¶ Indicates whether the (di)graph is connected. Note that in a graph, path connected is equivalent to connected.
INPUT:
G
(generic_graph) - the input graph.
See also
EXAMPLES:
sage: from sage.graphs.connectivity import is_connected sage: G = Graph( { 0 : [1, 2], 1 : [2], 3 : [4, 5], 4 : [5] } ) sage: is_connected(G) False sage: G.is_connected() False sage: G.add_edge(0,3) sage: is_connected(G) True sage: D = DiGraph( { 0 : [1, 2], 1 : [2], 3 : [4, 5], 4 : [5] } ) sage: is_connected(D) False sage: D.add_edge(0,3) sage: is_connected(D) True sage: D = DiGraph({1:[0], 2:[0]}) sage: is_connected(D) True
-
sage.graphs.connectivity.
is_cut_edge
¶ Returns True if the input edge is a cut-edge or a bridge.
A cut edge (or bridge) is an edge that when removed increases the number of connected components. This function works with simple graphs as well as graphs with loops and multiedges. In a digraph, a cut edge is an edge that when removed increases the number of (weakly) connected components.
INPUT: The following forms are accepted
- is_cut_edge(G, 1, 2 )
- is_cut_edge(G, (1, 2) )
- is_cut_edge(G, 1, 2, ‘label’ )
- is_cut_edge(G, (1, 2, ‘label’) )
OUTPUT:
- Returns True if (u,v) is a cut edge, False otherwise
EXAMPLES:
sage: from sage.graphs.connectivity import is_cut_edge sage: G = graphs.CompleteGraph(4) sage: is_cut_edge(G,0,2) False sage: G.is_cut_edge(0,2) False sage: G = graphs.CompleteGraph(4) sage: G.add_edge((0,5,'silly')) sage: is_cut_edge(G,(0,5,'silly')) True sage: G = Graph([[0,1],[0,2],[3,4],[4,5],[3,5]]) sage: is_cut_edge(G,(0,1)) True sage: G = Graph([[0,1],[0,2],[1,1]], loops = True) sage: is_cut_edge(G,(1,1)) False sage: G = digraphs.Circuit(5) sage: is_cut_edge(G,(0,1)) False sage: G = graphs.CompleteGraph(6) sage: is_cut_edge(G,(0,7)) Traceback (most recent call last): ... ValueError: edge not in graph
-
sage.graphs.connectivity.
is_cut_vertex
¶ Returns True if the input vertex is a cut-vertex.
A vertex is a cut-vertex if its removal from the (di)graph increases the number of (strongly) connected components. Isolated vertices or leafs are not cut-vertices. This function works with simple graphs as well as graphs with loops and multiple edges.
INPUT:
G
(generic_graph) - the input graph.u
– a vertexweak
– (default:False
) boolean set to \(True\) if the connectivity of directed graphs is to be taken in the weak sense, that is ignoring edges orientations.
OUTPUT:
Returns True if
u
is a cut-vertex, and False otherwise.EXAMPLES:
Giving a LollipopGraph(4,2), that is a complete graph with 4 vertices with a pending edge:
sage: from sage.graphs.connectivity import is_cut_vertex sage: G = graphs.LollipopGraph(4,2) sage: is_cut_vertex(G,0) False sage: is_cut_vertex(G,3) True sage: G.is_cut_vertex(3) True
Comparing the weak and strong connectivity of a digraph:
sage: from sage.graphs.connectivity import is_strongly_connected sage: D = digraphs.Circuit(6) sage: is_strongly_connected(D) True sage: is_cut_vertex(D,2) True sage: is_cut_vertex(D, 2, weak=True) False
Giving a vertex that is not in the graph:
sage: G = graphs.CompleteGraph(6) sage: is_cut_vertex(G,7) Traceback (most recent call last): ... ValueError: The input vertex is not in the vertex set.
-
sage.graphs.connectivity.
is_strongly_connected
¶ Returns whether the current
DiGraph
is strongly connected.EXAMPLES:
The circuit is obviously strongly connected
sage: from sage.graphs.connectivity import is_strongly_connected sage: g = digraphs.Circuit(5) sage: is_strongly_connected(g) True sage: g.is_strongly_connected() True
But a transitive triangle is not:
sage: g = DiGraph({ 0 : [1,2], 1 : [2]}) sage: is_strongly_connected(g) False
-
sage.graphs.connectivity.
strong_articulation_points
¶ Return the strong articulation points of this digraph.
A vertex is a strong articulation point if its deletion increases the number of strongly connected components. This method implements the algorithm described in [ILS2012]. The time complexity is dominated by the time complexity of the immediate dominators finding algorithm.
OUTPUT: The list of strong articulation points.
EXAMPLES:
Two cliques sharing a vertex:
sage: from sage.graphs.connectivity import strong_articulation_points sage: D = digraphs.Complete(4) sage: D.add_clique([3, 4, 5, 6]) sage: strong_articulation_points(D) [3] sage: D.strong_articulation_points() [3]
Two cliques connected by some arcs:
sage: D = digraphs.Complete(4) * 2 sage: D.add_edges([(0, 4), (7, 3)]) sage: sorted( strong_articulation_points(D) ) [0, 3, 4, 7] sage: D.add_edge(1, 5) sage: sorted( strong_articulation_points(D) ) [3, 7] sage: D.add_edge(6, 2) sage: strong_articulation_points(D) []
-
sage.graphs.connectivity.
strongly_connected_component_containing_vertex
¶ Returns the strongly connected component containing a given vertex
INPUT:
G
(DiGraph) - the input graph.v
– a vertex
EXAMPLES:
In the symmetric digraph of a graph, the strongly connected components are the connected components:
sage: from sage.graphs.connectivity import strongly_connected_component_containing_vertex sage: g = graphs.PetersenGraph() sage: d = DiGraph(g) sage: strongly_connected_component_containing_vertex(d,0) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sage: d.strongly_connected_component_containing_vertex(0) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
-
sage.graphs.connectivity.
strongly_connected_components_digraph
¶ Returns the digraph of the strongly connected components
INPUT:
G
(DiGraph) - the input graph.keep_labels
– boolean (default: False)
The digraph of the strongly connected components of a graph \(G\) has a vertex per strongly connected component included in \(G\). There is an edge from a component \(C_1\) to a component \(C_2\) if there is an edge from one to the other in \(G\).
EXAMPLES:
Such a digraph is always acyclic
sage: from sage.graphs.connectivity import strongly_connected_components_digraph sage: g = digraphs.RandomDirectedGNP(15,.1) sage: scc_digraph = strongly_connected_components_digraph(g) sage: scc_digraph.is_directed_acyclic() True sage: scc_digraph = g.strongly_connected_components_digraph() sage: scc_digraph.is_directed_acyclic() True
The vertices of the digraph of strongly connected components are exactly the strongly connected components:
sage: g = digraphs.ButterflyGraph(2) sage: scc_digraph = strongly_connected_components_digraph(g) sage: g.is_directed_acyclic() True sage: all([ Set(scc) in scc_digraph.vertices() for scc in g.strongly_connected_components()]) True
The following digraph has three strongly connected components, and the digraph of those is a chain:
sage: g = DiGraph({0:{1:"01", 2: "02", 3: "03"}, 1: {2: "12"}, 2:{1: "21", 3: "23"}}) sage: scc_digraph = strongly_connected_components_digraph(g) sage: scc_digraph.vertices() [{0}, {3}, {1, 2}] sage: scc_digraph.edges() [({0}, {1, 2}, None), ({0}, {3}, None), ({1, 2}, {3}, None)]
By default, the labels are discarded, and the result has no loops nor multiple edges. If
keep_labels
isTrue
, then the labels are kept, and the result is a multi digraph, possibly with multiple edges and loops. However, edges in the result with same source, target, and label are not duplicated (see the edges from 0 to the strongly connected component \(\{1,2\}\) below):sage: g = DiGraph({0:{1:"0-12", 2: "0-12", 3: "0-3"}, 1: {2: "1-2", 3: "1-3"}, 2:{1: "2-1", 3: "2-3"}}) sage: scc_digraph = strongly_connected_components_digraph(g, keep_labels = True) sage: scc_digraph.vertices() [{0}, {3}, {1, 2}] sage: scc_digraph.edges() [({0}, {1, 2}, '0-12'), ({0}, {3}, '0-3'), ({1, 2}, {1, 2}, '1-2'), ({1, 2}, {1, 2}, '2-1'), ({1, 2}, {3}, '1-3'), ({1, 2}, {3}, '2-3')]
-
sage.graphs.connectivity.
strongly_connected_components_subgraphs
¶ Returns the strongly connected components as a list of subgraphs.
EXAMPLES:
In the symmetric digraph of a graph, the strongly connected components are the connected components:
sage: from sage.graphs.connectivity import strongly_connected_components_subgraphs sage: g = graphs.PetersenGraph() sage: d = DiGraph(g) sage: strongly_connected_components_subgraphs(d) [Subgraph of (Petersen graph): Digraph on 10 vertices] sage: d.strongly_connected_components_subgraphs() [Subgraph of (Petersen graph): Digraph on 10 vertices]
-
sage.graphs.connectivity.
vertex_connectivity
¶ Return the vertex connectivity of the graph.
For more information, see Wikipedia article Connectivity_(graph_theory) and Wikipedia article K-vertex-connected_graph.
Note
- When the graph is directed, this method actually computes the
strong connectivity, (i.e. a directed graph is strongly
\(k\)-connected if there are \(k\) vertex disjoint paths between any
two vertices \(u, v\)). If you do not want to consider strong
connectivity, the best is probably to convert your
DiGraph
object to aGraph
object, and compute the connectivity of this other graph. - By convention, a complete graph on \(n\) vertices is \(n-1\) connected. In this case, no certificate can be given as there is no pair of vertices split by a cut of order \(k-1\). For this reason, the certificates returned in this situation are empty.
INPUT:
G
(generic_graph) - the input graph.value_only
– boolean (default:True
)- When set to
True
(default), only the value is returned. - When set to
False
, both the value and a minimum vertex cut are returned.
- When set to
sets
– boolean (default:False
)- When set to
True
, also returns the two sets of vertices that are disconnected by the cut. Impliesvalue_only=False
- When set to
k
– integer (default:None
) When specified, check if the vertex connectivity of the (di)graph is larger or equal to \(k\). The method thus outputs a boolean only.solver
– (default:None
) Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers, see the methodsolve
of the classMixedIntegerLinearProgram
. Use methodsage.numerical.backends.generic_backend.default_mip_solver()
to know which default solver is used or to set the default solver.verbose
– integer (default:0
). Sets the level of verbosity. Set to 0 by default, which means quiet.
EXAMPLES:
A basic application on a
PappusGraph
:sage: from sage.graphs.connectivity import vertex_connectivity sage: g=graphs.PappusGraph() sage: vertex_connectivity(g) 3 sage: g.vertex_connectivity() 3
In a grid, the vertex connectivity is equal to the minimum degree, in which case one of the two sets is of cardinality \(1\):
sage: g = graphs.GridGraph([ 3,3 ]) sage: [value, cut, [ setA, setB ]] = vertex_connectivity(g, sets=True) sage: len(setA) == 1 or len(setB) == 1 True
A vertex cut in a tree is any internal vertex:
sage: tree = graphs.RandomTree(15) sage: val, [cut_vertex] = vertex_connectivity(tree, value_only=False) sage: tree.degree(cut_vertex) > 1 True
When
value_only = True
, this function is optimized for small connectivity values and does not need to build a linear program.It is the case for connected graphs which are not connected:
sage: g = 2 * graphs.PetersenGraph() sage: vertex_connectivity(g) 0
Or if they are just 1-connected:
sage: g = graphs.PathGraph(10) sage: vertex_connectivity(g) 1
For directed graphs, the strong connectivity is tested through the dedicated function:
sage: g = digraphs.ButterflyGraph(3) sage: vertex_connectivity(g) 0
A complete graph on \(10\) vertices is \(9\)-connected:
sage: g = graphs.CompleteGraph(10) sage: vertex_connectivity(g) 9
A complete digraph on \(10\) vertices is \(9\)-connected:
sage: g = DiGraph(graphs.CompleteGraph(10)) sage: vertex_connectivity(g) 9
When parameter
k
is set, we only check for the existence of a vertex cut of order at leastk
:sage: g = graphs.PappusGraph() sage: vertex_connectivity(g, k=3) True sage: vertex_connectivity(g, k=4) False
- When the graph is directed, this method actually computes the
strong connectivity, (i.e. a directed graph is strongly
\(k\)-connected if there are \(k\) vertex disjoint paths between any
two vertices \(u, v\)). If you do not want to consider strong
connectivity, the best is probably to convert your