Types of Edges and Vertices
A vertex v is called a cut vertex of the graph G if removing the vertex v and the boundary edges from G results in more components than G. An edge e is called a cut edge of the graph G if removing the edge e from G results in more components than G. When an edge is removed from a graph, its vertices are left in. Vertices C, D, E, and G are cut vertices of the graph in the following figure, because removing them from the graph results in more components.
Figure. Cut Vertices, Cut Edges, and Cycle Vertices
The top of the following figure shows what happens when vertex E is cut from the graph, resulting in two components. Likewise, edges D-E and E-G are cut edges of the graph. The bottom of the following figure shows what happens when edge E-G is cut from the graph, resulting in two components. Vertices A, B, C, D, E, G, H, and I are cycle vertices of the graph depicted in the following figure.
Figure. Resulting Graphs Minus a Cut Vertex and a Cut Edge
Class methods from generic_graph associated with cut vertices and edges include cut_vertices, is_cut_vertex, cut_edges, and is_cut_edge. Scheme extensions include graph:cut-vertices, graph:cut_vertex?, graph:cut-edges, and graph:cut_edge?.
[Top]
© 1989-2007 Spatial Corp., a Dassault Systèmes company. All rights reserved.