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.
cleave()	Return the connected subgraphs separated by the input vertex cut.
spqr_tree()	Return a SPQR-tree representing the triconnected components of the graph.
spqr_tree_to_graph()	Return the graph represented by the SPQR-tree \(T\).

Methods

class sage.graphs.connectivity.TriconnectivitySPQR

Bases: object

Decompose a graph into triconnected components and build SPQR-tree.

This class implements the algorithm proposed by Hopcroft and Tarjan in [Hopcroft1973], and later corrected by Gutwenger and Mutzel in [Gut2001], for finding the triconnected components of a biconnected graph. It then organizes these components into a SPQR-tree. See the:wikipedia:\(SPQR_tree\).

A SPQR-tree is a tree data structure used to represent the triconnected components of a biconnected (multi)graph and the 2-vertex cuts separating them. A node of a SPQR-tree, and the graph associated with it, can be one of the following four types:

• "S" – the associated graph is a cycle with at least three vertices. "S" stands for series and is also called a polygon.
• "P" – the associated graph is a dipole graph, a multigraph with two vertices and three or more edges. "P" stands for parallel and the node is called a bond.
• "Q" – the associated graph has a single real edge. This trivial case is necessary to handle the graph that has only one edge.
• "R" – the associated graph is a 3-vertex-connected graph that is not a cycle or dipole. "R" stands for rigid.

The edges of the tree indicate the 2-vertex cuts of the graph.

INPUT:

• G – graph; if G is a DiGraph, the computation is done on the underlying Graph (i.e., ignoring edge orientation)
• check – boolean (default: True); indicates whether G needs to be tested for biconnectivity

See also

• sage.graphs.connectivity.spqr_tree()
• is_biconnected()
• Wikipedia article SPQR_tree

EXAMPLES:

Example from the Wikipedia article SPQR_tree:

sage: from sage.graphs.connectivity import TriconnectivitySPQR
sage: from sage.graphs.connectivity import spqr_tree_to_graph
sage: G = Graph([(1, 2), (1, 4), (1, 8), (1, 12), (3, 4), (2, 3),
....: (2, 13), (3, 13), (4, 5), (4, 7), (5, 6), (5, 8), (5, 7), (6, 7),
....: (8, 11), (8, 9), (8, 12), (9, 10), (9, 11), (9, 12), (10, 12)])
sage: tric = TriconnectivitySPQR(G)
sage: T = tric.get_spqr_tree()
sage: G.is_isomorphic(spqr_tree_to_graph(T))
True

An example from [Hopcroft1973]:

sage: G = Graph([(1, 2), (1, 4), (1, 8), (1, 12), (1, 13), (2, 3),
....: (2, 13), (3, 4), (3, 13), (4, 5), (4, 7), (5, 6), (5, 7), (5, 8),
....: (6, 7), (8, 9), (8, 11), (8, 12), (9, 10), (9, 11), (9, 12),
....: (10, 11), (10, 12)])
sage: tric = TriconnectivitySPQR(G)
sage: tric.print_triconnected_components()
Triconnected: [(3, 13, None), (1, 13, None), (2, 13, None), (2, 3, None), (1, 2, None), (3, 1, 'newVEdge0')]
Polygon: [(3, 4, None), (3, 1, 'newVEdge0'), (4, 1, 'newVEdge1')]
Bond: [(1, 4, None), (4, 1, 'newVEdge1'), (4, 1, 'newVEdge2')]
Polygon: [(6, 7, None), (5, 6, None), (7, 5, 'newVEdge3')]
Bond: [(7, 5, 'newVEdge3'), (5, 7, 'newVEdge4'), (5, 7, None)]
Polygon: [(5, 7, 'newVEdge4'), (4, 7, None), (5, 4, 'newVEdge5')]
Bond: [(4, 5, None), (5, 4, 'newVEdge5'), (5, 4, 'newVEdge6')]
Polygon: [(5, 4, 'newVEdge6'), (4, 1, 'newVEdge2'), (5, 8, None), (8, 1, 'newVEdge8')]
Bond: [(1, 8, None), (8, 1, 'newVEdge8'), (8, 1, 'newVEdge9')]
Triconnected: [(8, 9, None), (9, 12, None), (9, 11, None), (8, 11, None), (10, 11, None), (9, 10, None), (10, 12, None), (8, 12, 'newVEdge10')]
Bond: [(8, 12, 'newVEdge10'), (12, 8, 'newVEdge11'), (8, 12, None)]
Polygon: [(8, 1, 'newVEdge9'), (12, 8, 'newVEdge11'), (1, 12, None)]

An example from [Gut2001]:

sage: G = Graph([(1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (3, 5), (4, 5),
....: (4, 6), (5, 7), (5, 8), (5, 14), (6, 8), (7, 14), (8, 9), (8, 10),
....: (8, 11), (8, 12), (9, 10), (10, 13), (10, 14), (10, 15), (10, 16),
....: (11, 12), (11, 13), (12, 13), (14, 15), (14, 16), (15, 16)])
sage: T = TriconnectivitySPQR(G).get_spqr_tree()
sage: G.is_isomorphic(spqr_tree_to_graph(T))
True

An example with multi-edges and accessing the triconnected components:

sage: G = Graph([(1, 2), (1, 5), (1, 5), (2, 3), (2, 3), (3, 4), (4, 5)], multiedges=True)
sage: tric = TriconnectivitySPQR(G)
sage: tric.print_triconnected_components()
Bond:  [(1, 5, None), (1, 5, None), (1, 5, 'newVEdge0')]
Bond:  [(2, 3, None), (2, 3, None), (2, 3, 'newVEdge1')]
Polygon:  [(4, 5, None), (1, 5, 'newVEdge0'), (3, 4, None), (2, 3, 'newVEdge1'), (1, 2, None)]

An example of a triconnected graph:

sage: G = Graph([('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')])
sage: T = TriconnectivitySPQR(G).get_spqr_tree()
sage: print(T.vertices())
[('R', Multi-graph on 4 vertices)]
sage: G.is_isomorphic(spqr_tree_to_graph(T))
True

An example of a directed graph with multi-edges:

sage: G = DiGraph([(1, 2), (2, 3), (3, 4), (4, 5), (1, 5), (5, 1)])
sage: tric = TriconnectivitySPQR(G)
sage: tric.print_triconnected_components()
Bond:  [(1, 5, None), (5, 1, None), (1, 5, 'newVEdge0')]
Polygon:  [(4, 5, None), (1, 5, 'newVEdge0'), (3, 4, None), (2, 3, None), (1, 2, None)]

Edge labels are preserved by the construction:

sage: G = Graph([(0, 1, '01'), (0, 4, '04'), (1, 2, '12'), (1, 5, '15'),
....: (2, 3, '23'), (2, 6, '26'), (3, 7, '37'), (4, 5, '45'),
....: (5, 6, '56'), (6, 7, 67)])
sage: T = TriconnectivitySPQR(G).get_spqr_tree()
sage: H = spqr_tree_to_graph(T)
sage: set(G.edges()) == set(H.edges())
True

Todo

Cythonize the code for more efficiency. Many data structures can be turned into integer arrays. More care is needed for the doubly linked list and for the lists of lists. Note that the internal graph copy must allow edge addition due to the insertion of virtual edges.

get_spqr_tree()

Return an SPQR-tree representing the triconnected components of the graph.

An SPQR-tree is a tree data structure used to represent the triconnected components of a biconnected (multi)graph and the 2-vertex cuts separating them. A node of a SPQR-tree, and the graph associated with it, can be one of the following four types:

• "S" – the associated graph is a cycle with at least three vertices. "S" stands for series.
• "P" – the associated graph is a dipole graph, a multigraph with two vertices and three or more edges. "P" stands for parallel.
• "Q" – the associated graph has a single real edge. This trivial case is necessary to handle the graph that has only one edge.
• "R" – the associated graph is a 3-connected graph that is not a cycle or dipole. "R" stands for rigid.

The edges of the tree indicate the 2-vertex cuts of the graph.

OUTPUT:

SPQR-tree a tree whose vertices are labeled with the block’s type and the subgraph of three-blocks in the decomposition.

EXAMPLES:

sage: from sage.graphs.connectivity import TriconnectivitySPQR
sage: G = Graph(2)
sage: for i in range(3):
....:     G.add_clique([0, 1, G.add_vertex(), G.add_vertex()])
sage: tric = TriconnectivitySPQR(G)
sage: Tree = tric.get_spqr_tree()
sage: K4 = graphs.CompleteGraph(4)
sage: all(u[1].is_isomorphic(K4) for u in Tree.vertices() if u[0] == 'R')
True
sage: from sage.graphs.connectivity import spqr_tree_to_graph
sage: G.is_isomorphic(spqr_tree_to_graph(Tree))
True

sage: G = Graph(2)
sage: for i in range(3):
....:     G.add_path([0, G.add_vertex(), G.add_vertex(), 1])
sage: tric = TriconnectivitySPQR(G)
sage: Tree = tric.get_spqr_tree()
sage: C4 = graphs.CycleGraph(4)
sage: all(u[1].is_isomorphic(C4) for u in Tree.vertices() if u[0] == 'S')
True
sage: G.is_isomorphic(spqr_tree_to_graph(Tree))
True

sage: G.allow_multiple_edges(True)
sage: G.add_edges(G.edges())
sage: tric = TriconnectivitySPQR(G)
sage: Tree = tric.get_spqr_tree()
sage: all(u[1].is_isomorphic(C4) for u in Tree.vertices() if u[0] == 'S')
True
sage: G.is_isomorphic(spqr_tree_to_graph(Tree))
True

sage: G = graphs.CycleGraph(6)
sage: tric = TriconnectivitySPQR(G)
sage: Tree = tric.get_spqr_tree()
sage: Tree.order()
1
sage: G.is_isomorphic(spqr_tree_to_graph(Tree))
True
sage: G.add_edge(0, 3)
sage: tric = TriconnectivitySPQR(G)
sage: Tree = tric.get_spqr_tree()
sage: Tree.order()
3
sage: G.is_isomorphic(spqr_tree_to_graph(Tree))
True

sage: G = Graph([(0, 1)], multiedges=True)
sage: tric = TriconnectivitySPQR(G)
sage: Tree = tric.get_spqr_tree()
sage: Tree.vertices()
[('Q', Multi-graph on 2 vertices)]
sage: G.add_edge(0, 1)
sage: Tree = TriconnectivitySPQR(G).get_spqr_tree()
sage: Tree.vertices()
[('P', Multi-graph on 2 vertices)]

get_triconnected_components()

Return the triconnected components as a list of tuples.

Each component is represented as a tuple of the type of the component and the list of edges of the component.

EXAMPLES:

sage: from sage.graphs.connectivity import TriconnectivitySPQR
sage: G = Graph(2)
sage: for i in range(3):
....:     G.add_path([0, G.add_vertex(), G.add_vertex(), 1]) 
sage: tric = TriconnectivitySPQR(G)
sage: tric.get_triconnected_components()
[('Polygon', [(4, 5, None), (0, 4, None), (1, 5, None), (1, 0, 'newVEdge1')]),
('Polygon', [(6, 7, None), (0, 6, None), (1, 7, None), (1, 0, 'newVEdge3')]),
('Bond', [(1, 0, 'newVEdge1'), (1, 0, 'newVEdge3'), (1, 0, 'newVEdge4')]),
('Polygon', [(1, 3, None), (1, 0, 'newVEdge4'), (2, 3, None), (0, 2, None)])]

print_triconnected_components()

Print the type and list of edges of each component.

EXAMPLES:

An example from [Hopcroft1973]:

sage: from sage.graphs.connectivity import TriconnectivitySPQR
sage: G = Graph([(1, 2), (1, 4), (1, 8), (1, 12), (1, 13), (2, 3),
....: (2, 13), (3, 4), (3, 13), (4, 5), (4, 7), (5, 6), (5, 7), (5, 8),
....: (6, 7), (8, 9), (8, 11), (8, 12), (9, 10), (9, 11), (9, 12),
....: (10, 11), (10, 12)])
sage: tric = TriconnectivitySPQR(G)
sage: tric.print_triconnected_components()
Triconnected: [(3, 13, None), (1, 13, None), (2, 13, None), (2, 3, None), (1, 2, None), (3, 1, 'newVEdge0')]
Polygon: [(3, 4, None), (3, 1, 'newVEdge0'), (4, 1, 'newVEdge1')]
Bond: [(1, 4, None), (4, 1, 'newVEdge1'), (4, 1, 'newVEdge2')]
Polygon: [(6, 7, None), (5, 6, None), (7, 5, 'newVEdge3')]
Bond: [(7, 5, 'newVEdge3'), (5, 7, 'newVEdge4'), (5, 7, None)]
Polygon: [(5, 7, 'newVEdge4'), (4, 7, None), (5, 4, 'newVEdge5')]
Bond: [(4, 5, None), (5, 4, 'newVEdge5'), (5, 4, 'newVEdge6')]
Polygon: [(5, 4, 'newVEdge6'), (4, 1, 'newVEdge2'), (5, 8, None), (8, 1, 'newVEdge8')]
Bond: [(1, 8, None), (8, 1, 'newVEdge8'), (8, 1, 'newVEdge9')]
Triconnected: [(8, 9, None), (9, 12, None), (9, 11, None), (8, 11, None), (10, 11, None), (9, 10, None), (10, 12, None), (8, 12, 'newVEdge10')]
Bond: [(8, 12, 'newVEdge10'), (12, 8, 'newVEdge11'), (8, 12, None)]
Polygon: [(8, 1, 'newVEdge9'), (12, 8, 'newVEdge11'), (1, 12, None)]

sage.graphs.connectivity.blocks_and_cut_vertices

Compute 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 blocks

  and 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), where B is a list of blocks - each is a list of vertices and the blocks are the corresponding induced subgraphs - and C 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

• blocks_and_cuts_tree()
• sage.graphs.base.boost_graph.blocks_and_cut_vertices()
• is_biconnected()
• bridges()

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])

A directed graph with Boost’s algorithm (trac ticket #25994):

sage: rings = graphs.CycleGraph(10)
sage: rings.merge_vertices([0, 5])
sage: rings = rings.to_directed()
sage: blocks_and_cut_vertices(rings, algorithm="Tarjan_Boost")
([[0, 1, 4, 2, 3], [0, 6, 9, 7, 8]], [0])

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.

See also

• blocks_and_cut_vertices()
• is_biconnected()

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) if False, 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.cleave

Return the connected subgraphs separated by the input vertex cut.

Given a connected (multi)graph \(G\) and a vertex cut \(X\), this method computes the list of subgraphs of \(G\) induced by each connected component \(c\) of \(G\setminus X\) plus \(X\), i.e., \(G[c\cup X]\).

INPUT:

• G – a Graph.
• cut_vertices – (default: None) a set of vertices representing a vertex cut of G. If no vertex cut is given, the method will compute one via a call to vertex_connectivity().
• virtual_edges – boolean (default: True); whether to add virtual edges to the sides of the cut or not. A virtual edge is an edge between a pair of vertices of the cut that are not connected by an edge in G.
• solver – (default: None) Specify a Linear Program (LP) solver to be used. If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method sage.numerical.mip.MixedIntegerLinearProgram.solve() of the class sage.numerical.mip.MixedIntegerLinearProgram.
• verbose – integer (default: 0). Sets the level of verbosity. Set to 0 by default, which means quiet.

OUTPUT: A triple \((S, C, f)\), where

• \(S\) is a list of the graphs that are sides of the vertex cut.
• \(C\) is the graph of the cocycles. For each pair of vertices of the cut, if there exists an edge between them, \(C\) has one copy of each edge connecting them in G per sides of the cut plus one extra copy. Furthermore, when virtual_edges == True, if a pair of vertices of the cut is not connected by an edge in G, then it has one virtual edge between them per sides of the cut.
• \(f\) is the complement of the subgraph of G induced by the vertex cut. Hence, its vertex set is the vertex cut, and its edge set is the set of virtual edges (i.e., edges between pairs of vertices of the cut that are not connected by an edge in G). When virtual_edges == False, the edge set is empty.

EXAMPLES:

If there is an edge between cut vertices:

sage: from sage.graphs.connectivity import cleave
sage: G = Graph(2)
sage: for _ in range(3):
....:     G.add_clique([0, 1, G.add_vertex(), G.add_vertex()])
sage: S1,C1,f1 = cleave(G, cut_vertices=[0, 1])
sage: [g.order() for g in S1]
[4, 4, 4]
sage: C1.order(), C1.size()
(2, 4)
sage: f1.vertices(), f1.edges()
([0, 1], [])

If virtual_edges == False and there is an edge between cut vertices:

sage: G.subgraph([0, 1]).complement() == Graph([[0, 1], []])
True
sage: S2,C2,f2 = cleave(G, cut_vertices=[0, 1], virtual_edges = False)
sage: (S1 == S2, C1 == C2, f1 == f2)
(True, True, True)

If cut vertices doesn’t have edge between them:

sage: G.delete_edge(0, 1)
sage: S1,C1,f1 = cleave(G, cut_vertices=[0, 1])
sage: [g.order() for g in S1]
[4, 4, 4]
sage: C1.order(), C1.size()
(2, 3)
sage: f1.vertices(), f1.edges()
([0, 1], [(0, 1, None)])

If virtual_edges == False and the cut vertices are not connected by an edge:

sage: G.subgraph([0, 1]).complement() == Graph([[0, 1], []])
False
sage: S2,C2,f2 = cleave(G, cut_vertices=[0, 1], virtual_edges = False)
sage: [g.order() for g in S2]
[4, 4, 4]
sage: C2.order(), C2.size()
(2, 0)
sage: f2.vertices(), f2.edges()
([0, 1], [])
sage: (S1 == S2, C1 == C2, f1 == f2)
(False, False, False)

If \(G\) is a biconnected multigraph:

sage: G = graphs.CompleteBipartiteGraph(2,3)
sage: G.add_edge(2, 3)
sage: G.allow_multiple_edges(True)
sage: G.add_edges(G.edges())
sage: G.add_edges([(0, 1), (0, 1), (0, 1)])
sage: S,C,f = cleave(G, cut_vertices=[0, 1])
sage: for g in S:
....:     print(g.edges(labels=0))
[(0, 1), (0, 1), (0, 1), (0, 2), (0, 2), (0, 3), (0, 3), (1, 2), (1, 2), (1, 3), (1, 3), (2, 3), (2, 3)]
[(0, 1), (0, 1), (0, 1), (0, 4), (0, 4), (1, 4), (1, 4)]

sage.graphs.connectivity.connected_component_containing_vertex

Return a list of the vertices connected to vertex.

INPUT:

• G (generic_graph) – the input graph.
• v – the vertex to search for.
• sort – boolean (default True) whether to sort vertices inside the component

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

Return the list of connected components.

This 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.
• sort – boolean (default True) whether to sort vertices inside each component

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

Return 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

Return 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 Connectivity_(graph_theory).

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 a Graph 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.
• 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 when edge_labels=True, and it is unreliable for directed graphs (see trac ticket #18753).
  • When set to "Sage", we use Sage’s implementation.
• 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.). Implies boost = False.
  • When set to False, each edge has weight \(1\).
• vertices – boolean (default: False)
  • When set to True, also returns the two sets of vertices that are disconnected by the cut. Implies value_only=False.
• solver – (default: None) Specify a Linear Program (LP) solver to be used (ignored if implementation='boost'). If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
• 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 and implementation="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

Test 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

• is_biconnected()

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 vertex
• weak – (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.spqr_tree

Return an SPQR-tree representing the triconnected components of the graph.

An SPQR-tree is a tree data structure used to represent the triconnected components of a biconnected (multi)graph and the 2-vertex cuts separating them. A node of a SPQR-tree, and the graph associated with it, can be one of the following four types:

• "S" – the associated graph is a cycle with at least three vertices. "S" stands for series.
• "P" – the associated graph is a dipole graph, a multigraph with two vertices and three or more edges. "P" stands for parallel.
• "Q" – the associated graph has a single real edge. This trivial case is necessary to handle the graph that has only one edge.
• "R" – the associated graph is a 3-connected graph that is not a cycle or dipole. "R" stands for rigid.

This method decomposes a biconnected graph into cycles, cocycles, and 3-connected blocks summed over cocycles, and arranges them as a SPQR-tree. More precisely, it splits the graph at each of its 2-vertex cuts, giving a unique decomposition into 3-connected blocks, cycles and cocycles. The cocycles are dipole graphs with one edge per real edge between the included vertices and one additional (virtual) edge per connected component resulting from deletion of the vertices in the cut. See the Wikipedia article SPQR_tree.

INPUT:

• G - the input graph.

• algorithm – The algorithm to use in computing the SPQR tree of G.

  The following algorithms are supported:

  • "Hopcroft_Tarjan" (default) – Use the algorithm proposed by Hopcroft and Tarjan in [Hopcroft1973] and later corrected by Gutwenger and Mutzel in [Gut2001]. See TriconnectivitySPQR.
  • "cleave" – Using method cleave().

• solver – (default: None) Specify a Linear Program (LP) solver to be used. If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method sage.numerical.mip.MixedIntegerLinearProgram.solve() of the class sage.numerical.mip.MixedIntegerLinearProgram.

• verbose – integer (default: 0). Sets the level of verbosity. Set to 0 by default, which means quiet.

OUTPUT: SPQR-tree a tree whose vertices are labeled with the block’s type and the subgraph of three-blocks in the decomposition.

EXAMPLES:

sage: from sage.graphs.connectivity import spqr_tree
sage: G = Graph(2)
sage: for i in range(3):
....:     G.add_clique([0, 1, G.add_vertex(), G.add_vertex()])
sage: Tree = spqr_tree(G)
sage: Tree.order()
4
sage: K4 = graphs.CompleteGraph(4)
sage: all(u[1].is_isomorphic(K4) for u in Tree.vertices() if u[0] == 'R')
True
sage: from sage.graphs.connectivity import spqr_tree_to_graph
sage: G.is_isomorphic(spqr_tree_to_graph(Tree))
True

sage: G = Graph(2)
sage: for i in range(3):
....:     G.add_path([0, G.add_vertex(), G.add_vertex(), 1])
sage: Tree = spqr_tree(G)
sage: Tree.order()
4
sage: C4 = graphs.CycleGraph(4)
sage: all(u[1].is_isomorphic(C4) for u in Tree.vertices() if u[0] == 'S')
True
sage: G.is_isomorphic(spqr_tree_to_graph(Tree))
True

sage: G.allow_multiple_edges(True)
sage: G.add_edges(G.edges())
sage: Tree = spqr_tree(G)
sage: Tree.order()
13
sage: all(u[1].is_isomorphic(C4) for u in Tree.vertices() if u[0] == 'S')
True
sage: G.is_isomorphic(spqr_tree_to_graph(Tree))
True

sage: G = graphs.CycleGraph(6)
sage: Tree = spqr_tree(G)
sage: Tree.order()
1
sage: G.is_isomorphic(spqr_tree_to_graph(Tree))
True
sage: G.add_edge(0, 3)
sage: Tree = spqr_tree(G)
sage: Tree.order()
3
sage: G.is_isomorphic(spqr_tree_to_graph(Tree))
True

sage: G = Graph('LlCG{O@?GBoMw?')
sage: T = spqr_tree(G, algorithm="Hopcroft_Tarjan")
sage: G.is_isomorphic(spqr_tree_to_graph(T))
True
sage: T2 = spqr_tree(G, algorithm='cleave')
sage: G.is_isomorphic(spqr_tree_to_graph(T2))
True

sage: G = Graph([(0, 1)], multiedges=True)
sage: T = spqr_tree(G, algorithm='cleave')
sage: T.vertices()
[('Q', Multi-graph on 2 vertices)]
sage: G.is_isomorphic(spqr_tree_to_graph(T))
True
sage: T = spqr_tree(G, algorithm='Hopcroft_Tarjan')
sage: T.vertices()
[('Q', Multi-graph on 2 vertices)]
sage: G.add_edge(0, 1)
sage: spqr_tree(G, algorithm='cleave').vertices()
[('P', Multi-graph on 2 vertices)]

sage: from collections import Counter
sage: G = graphs.PetersenGraph()
sage: T = G.spqr_tree(algorithm="Hopcroft_Tarjan")
sage: Counter(u[0] for u in T)
Counter({'R': 1})
sage: T = G.spqr_tree(algorithm="cleave")
sage: Counter(u[0] for u in T)
Counter({'R': 1})
sage: for u,v in G.edges(labels=False):
....:     G.add_path([u, G.add_vertex(), G.add_vertex(), v])
sage: T = G.spqr_tree(algorithm="Hopcroft_Tarjan")
sage: Counter(u[0] for u in T)
Counter({'P': 15, 'S': 15, 'R': 1})
sage: T = G.spqr_tree(algorithm="cleave")
sage: Counter(u[0] for u in T)
Counter({'P': 15, 'S': 15, 'R': 1})
sage: for u,v in G.edges(labels=False):
....:     G.add_path([u, G.add_vertex(), G.add_vertex(), v])
sage: T = G.spqr_tree(algorithm="Hopcroft_Tarjan")
sage: Counter(u[0] for u in T)
Counter({'S': 75, 'P': 60, 'R': 1})
sage: T = G.spqr_tree(algorithm="cleave") # long time
sage: Counter(u[0] for u in T)            # long time
Counter({'S': 75, 'P': 60, 'R': 1})

sage.graphs.connectivity.spqr_tree_to_graph

Return the graph represented by the SPQR-tree \(T\).

The main purpose of this method is to test spqr_tree().

INPUT:

• T – a SPQR tree as returned by spqr_tree().

OUTPUT: a (multi) graph

EXAMPLES:

Wikipedia article SPQR_tree reference paper example:

sage: from sage.graphs.connectivity import spqr_tree
sage: from sage.graphs.connectivity import spqr_tree_to_graph
sage: G = Graph([(1, 2), (1, 4), (1, 8), (1, 12), (3, 4), (2, 3),
....: (2, 13), (3, 13), (4, 5), (4, 7), (5, 6), (5, 8), (5, 7), (6, 7),
....: (8, 11), (8, 9), (8, 12), (9, 10), (9, 11), (9, 12), (10, 12)])
sage: T = spqr_tree(G)
sage: H = spqr_tree_to_graph(T)
sage: H.is_isomorphic(G)
True

A small multigraph

sage: G = Graph([(0, 2), (0, 2), (1, 3), (2, 3)], multiedges=True)
sage: for i in range(3):
....:     G.add_clique([0, 1, G.add_vertex(), G.add_vertex()])
sage: for i in range(3):
....:     G.add_clique([2, 3, G.add_vertex(), G.add_vertex()])
sage: T = spqr_tree(G)
sage: H = spqr_tree_to_graph(T)
sage: H.is_isomorphic(G)
True

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)
[]

See also

• strongly_connected_components()
• dominator_tree()

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(key=sorted)
[{0}, {1, 2}, {3}]
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 is True, 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(key=sorted)
[{0}, {1, 2}, {3}]
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 the Wikipedia article Connectivity_(graph_theory) and the 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 a Graph 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.
• sets – boolean (default: False)
  • When set to True, also returns the two sets of vertices that are disconnected by the cut. Implies value_only=False
• 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 to None, the default one is used. For more information on LP solvers, see the method solve of the class MixedIntegerLinearProgram. Use method sage.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 least k:

sage: g = graphs.PappusGraph()
sage: vertex_connectivity(g, k=3)
True
sage: vertex_connectivity(g, k=4)
False