Edge contraction

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Edge contraction.svg

In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex identification is a less restrictive form of this operation.

Definition[edit]

The edge contraction operation occurs relative to a particular edge, e. The edge e is removed and its two incident vertices, u and v, are merged into a new vertex w, where the edges incident to w each correspond to an edge incident to either u or v.

More generally, the operation may be performed on a set of edges by contracting each edge (in any order).[1] Contractions may result in a graph with loops or multiple edges.[2] These are sometimes deleted in order to stay within the class of simple graphs.

Formal definition[edit]

Let G=(V,E) be a graph (or directed graph) containing an edge e=(u,v) with uv. Let f be a function which maps every vertex in V\{u,v} to itself, and otherwise, maps it to a new vertex w. The contraction of e results in a new graph G′=(V′,E′), where V′=(V\{u,v})∪{w}, E′=E\{e}, and for every xV, x′=f(x)∈V′ is incident to an edge e′E′ if and only if, the corresponding edge, eE is incident to x in G.

Vertex identification[edit]

Vertex identification (sometimes called vertex contraction) removes the restriction that the contraction must occur over vertices sharing an incident edge. (Thus, edge contraction is a special case of vertex identification.) The operation may occur on any pair (or subset) of vertices in the graph. Edges between two contracting vertices are sometimes removed. If v and v' are vertices of distinct components of G, then we can create a new graph G' by identifying v and v' in G as a new vertex v in G'.[3]

Vertex Cleaving[edit]

Vertex cleaving which is the same as vertex splitting, means one vertex is being split into two, where these two new vertices are adjacent to the vertices that the original vertex was adjacent to. This is the reverse operation of vertex identification.

Path contraction[edit]

Path contraction occurs upon the set of edges in a path that contract to form a single edge between the endpoints of the path. Edges incident to vertices along the path are either eliminated, or arbitrarily (or systematically) connected to one of the endpoints.

Twisting[edit]

Given two disjoint graphs G1 and G2, where G1 contains vertices u1 and v1 and G2 contains vertices u2 and v2. Suppose we can obtain the graph G by identifying the vertices u1 of G1 and u2 of G2 as the vertex u of G and identifying the vertices v1 of G1 and v2 of G2 as the vertex v of G. In a twisting G' of G with respect to the vertex set {u, v}, we identify, instead, u1 with v2 and v1 with u2.[4]

Applications[edit]

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.

Edge contraction is used in the recursive formula for the number of spanning trees of an arbitrary connected graph,[5] and in the recurrence formula for the chromatic polynomial of a simple graph.[6]

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.

Edge contraction is used in 3D modelling packages (either manually, or through some feature of the modelling software) to consistently reduce vertex count, aiding in the creation of low-polygon models.

See also[edit]

Notes[edit]

  1. ^ Gross & Yellen 1998, p. 264
  2. ^ Loops may arise when the graph started with multiple edges or, even if the graph was simple, from the repeated application of edge contraction.
  3. ^ Oxley 1992, pp. 147-148
  4. ^ Oxley 1992, p. 148
  5. ^ Gross & Yellen 1998, p. 264
  6. ^ West 2001, p. 221

References[edit]

  • Gross, Jonathan; Yellen, Jay (1998), Graph Theory and its applications, CRC Press, ISBN 0-8493-3982-0 
  • Oxley, James (1992), Matroid Theory, Oxford University Press 
  • West, Douglas B. (2001), Introduction to Graph Theory (2nd ed.), Prentice-Hall, ISBN 0-13-014400-2 

External links[edit]