To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Edge contraction

From Wikipedia, the free encyclopedia

Contracting the edge between the indicated vertices, resulting in graph G / {uv}.

In graph theory, an edge contraction is an operation that 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.

YouTube Encyclopedic

  • 1/5
    Views:
    18 884
    915
    382
    1 232
    10 405
  • Graph Theory: 62. Graph Minors and Wagner's Theorem
  • Edge Subtraction and Bridges in Graphs | Graph Theory, Edge Deletion
  • Algorithms - Random Contraction Algorithm
  • 2556C04 - Feature-Preserving Mesh Simplification Using Reeb-Graph Topological Information
  • edge and vertex cuts

Transcription

Definition

The edge contraction operation occurs relative to a particular edge, . The edge is removed and its two incident vertices, and , are merged into a new vertex , where the edges incident to each correspond to an edge incident to either or . More generally, the operation may be performed on a set of edges by contracting each edge (in any order).[1]

The resulting graph is sometimes written as . (Contrast this with , which means removing the edge .)

Contracting an edge without creating multiple edges.

As defined below, an edge contraction operation may result in a graph with multiple edges even if the original graph was a simple graph.[2] However, some authors[3] disallow the creation of multiple edges, so that edge contractions performed on simple graphs always produce simple graphs.

Formal definition

Let be a graph (or directed graph) containing an edge with . Let be a function that maps every vertex in to itself, and otherwise, maps it to a new vertex . The contraction of results in a new graph , where , , and for every , is incident to an edge if and only if, the corresponding edge, is incident to in .

Vertex identification

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 and are vertices of distinct components of , then we can create a new graph by identifying and in as a new vertex in .[4] More generally, given a partition of the vertex set, one can identify vertices in the partition; the resulting graph is known as a quotient graph.

Vertex cleaving

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 a reverse operation of vertex identification, although in general for vertex identification, adjacent vertices of the two identified vertices are not the same set.

Path contraction

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

Consider two disjoint graphs and , where contains vertices and and contains vertices and . Suppose we can obtain the graph by identifying the vertices of and of as the vertex of and identifying the vertices of and of as the vertex of . In a twisting of with respect to the vertex set , we identify, instead, with and with .[5]

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.

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

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

Notes

  1. ^ Gross & Yellen 1998, p. 264
  2. ^ Also, 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. ^ Rosen 2011, p. 664
  4. ^ Oxley 2006, pp. 147–8 §5.3 Whitney's 2-Isomorphism Theorem
  5. ^ Oxley 2006, p. 148
  6. ^ Gross & Yellen 1998, p. 264
  7. ^ West 2001, p. 221

References

  • Gross, Jonathan; Yellen, Jay (1998), Graph Theory and its applications, CRC Press, ISBN 0-8493-3982-0
  • Oxley, James (2006) [1992], Matroid Theory, Oxford University Press, ISBN 978-0-19-920250-8
  • Rosen, Kenneth (2011), Discrete Mathematics and Its Applications (7th ed.), McGraw-Hill, ISBN 978-0-07-338309-5
  • West, Douglas B. (2001), Introduction to Graph Theory (2nd ed.), Prentice-Hall, ISBN 0-13-014400-2

External links

This page was last edited on 9 February 2024, at 17:10
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.