Edge contraction
From Wikipedia, the free encyclopedia
In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging together the two vertices it used to connect. All other edges incident to either of the two vertices become incident to the single merged vertex. More generally, we can contract a set of edges by contracting each of them individually. A similar operation is vertex contraction, where we merge together two or more vertices, removing any edges between two of the vertices being contracted.
Formally, let G=(V,E) be a graph containing an edge (u,v), and let G' be the result of contracting that edge. We define G' = (V', f(E')), where V' = V \ {u,v} U {w}, E' = E \ {(u,v)}, and f:E'→(V'×V') is defined by:
Another related operation, sometimes called path contraction, is where we take a non-branching path of edges and contract it into a single edge. Edges to or from vertices along the path are either forbidden, arbitrarily connected to either endpoint of the new edge, or systematically connected to one endpoint.
[edit] Applications
Both edge and vertex contraction techniques are valuable in proof by induction on the number of vertices or edges in a graph, where it can be assumed that a property holds for all smaller graphs and this can be used to prove the property for the larger graph.
Contractions are also useful in structures where we wish to simplify a graph by identifying vertices that represent essentially equivalent entities. One of the most common examples is the reduction of a general directed graph to an acyclic directed graph by contracting all of the vertices in each strongly connected component. If the relation described by the graph is transitive, no information is lost as long as we label each vertex with the set of labels of the vertices that were contracted to form it.
Another example is the coalescing performed in global graph coloring register allocation, where vertices are contracted (where it is safe) in order to eliminate move operations between distinct variables.
