3.2 Reduced Graph
A reduced graph, , is a data structure that supports the systematic elimination of all vertices from the graph . The vertices of the reduced graph are denoted as and its edges as . A crucial attribute of the reduced graph is efficient identification of the vertex in with the minimum degree.
A reduced graph supports the following operations:
Increase_degree increases the degree of vertex in by one.
Decrease_degree decreases the degree of vertex in by one.
Remove excises vertex from $ .
In_graph tests to see whether vertex is in .
Minimum_degree finds the vertex in with the smallest degree.
The topic of vertex elimination and efficient techniques for facilitating the elimination of many vertices are examined in detail in Section 8 of this document.