|
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 Figure 5-8, because removing them from the graph results in more components.
|
|
|
|
|
Figure 5-8. Cut Vertices, Cut Edges, and Cycle Vertices
|
|
|
Figure 5-9 top 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. Figure 5-9 bottom 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 Figure 5-8.
|
|
|
|
|
Figure 5-9. 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?.
|