Connectivity

Connectivity

Components

• is_connected(G): determine if the graph is connected.
• is_tree(G): determine if the graph is a tree.
• num_components(G): number of connected components.
• components(G): partition the vertex set of G into its connected components. Returns a Partition (see the SimplePartitions module).
• max_component(G): returns the vertex set of a largest (most vertices) component of G.
• spanning_forest(G): returns a maximal spanning forest of the graph.
• random_spanning_forest(G): also returns a maximal spanning forest, but may be different each time called.
• is_cut_vertex(G,v): determine if v is a cut vertex of G.
• is_cut_edge(G,v,w): determine if {v,w} is a cut edge of G. Also is_cut_edge(G,e).

Distance

Note: Distance functions give Int values and return -1 (instead of infinity) in case vertices are in different components. So diam(G) returns -1 if the graph is not connected.

• find_path(G,v,w): find a path between two vertices.
• dist(G,v,w): distance from between v and w.
• dist(G,v): list of distances from v to other vertices.
• dist(G): dictionary d with d[v,w] giving the distance between the vertices.
• dist_matrix(G): matrix of vertex-vertex distances.
• diam(G): diameter of G.
• eccentricity(G,v): maximum distance from v to another vertex.
• radius(G): minimum eccentricity.
• weiner_index(G): Weiner index.
• center(G): set of vertices with minimum eccentricities.

Bisection

• bisect(G,...) partitions the vertex set using the eigenvector associated with the second smallest eigenvalue of the graph's Laplacian matrix. Various options are available.

• cross_edges(G,A,B) returns the set of edges with one end in A and the other in B.

Vertex and Edge Connectivity

The functions connectivity and edge_connectivity are available in the SimpleGraphAlgorithms module.