3.2 Reduced Graph

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

A reduced graph supports the following operations:

• Increase_degree increases the degree of vertex $v$ in $V^{\prime}(G^{\prime})$ by one.

• Decrease_degree decreases the degree of vertex $v$ in $V^{\prime}(G^{\prime})$ by one.

• Remove excises vertex $v$ from $$V^{\prime}(G^{\prime})$ .

• In_graph tests to see whether vertex $v$ is in $V^{\prime}(G^{\prime})$.

• Minimum_degree finds the vertex $v$ in $V^{\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.