3.2 Reduced Graph

A reduced graph, G=V,EG^{\prime}=(V^{\prime},E^{\prime}), is a data structure that supports the systematic elimination of all vertices from the graph G=V,EG=(V,E). The vertices of the reduced graph are denoted as VGV^{\prime}(G^{\prime}) and its edges as EGE^{\prime}(G^{\prime}). A crucial attribute of the reduced graph is efficient identification of the vertex in VGV^{\prime}(G^{\prime}) with the minimum degree.

A reduced graph supports the following operations:

  • Increase_degree increases the degree of vertex vv in VGV^{\prime}(G^{\prime}) by one.

  • Decrease_degree decreases the degree of vertex vv in VGV^{\prime}(G^{\prime}) by one.

  • Remove excises vertex vv from $VGV^{\prime}(G^{\prime}) .

  • In_graph tests to see whether vertex vv is in VGV^{\prime}(G^{\prime}).

  • Minimum_degree finds the vertex vv in VGV^{\prime}(G^{\prime}) 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.