Lecture
In graph theory, edge contraction — is an operation that removes an edge from a graph while merging the two vertices that were previously joined by that edge into a single vertex. Edge contraction is a fundamental operation in the theory of graph minors. Vertex identification is another form of this operation with weaker restrictions.
The edge contraction operation is performed on a specific 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 correspond to the edges incident to either u or v. More generally, the operation can be carried out on a set of edges by contracting the edges of the set (in any order) .
As defined below, the edge contraction operation may produce a graph with multiple edges even if the original graph was a simple graph . However, some authors do not allow the creation of multiple edges, so that contracting edges in a simple graph always yields simple graphs.
Let G=(V,E) — be a graph (or a directed graph) containing an edge e=(u,v) with u≠v. Let f — be a function that maps any vertex in V to itself, and otherwise — to the vertex w. The contraction of e results in a new graph G′=(V′,E′), where V′=(V)∪{w}, E′=E, and for any vertex x∈V, the vertex x′=f(x)∈V′ is incident to the edge e′∈E′ if and only if the corresponding edge e∈E is incident to x in G.
Vertex identification (sometimes called vertex contraction) does not use the restriction that the contraction must be carried out on vertices incident to a single edge (thus, edge contraction is a special case of vertex identification). This operation can be performed on any pair (or subset) of vertices in the graph. The edges between the two contracted vertices are sometimes removed. If v and v' — are vertices of different components of the graph G, then we can create a new graph G' by identifying v and v' in G into a new vertex v in G' .
Vertex splitting means replacing one vertex with two, and these two new vertices are adjacent to the vertices to which the original vertex was adjacent. The operation is the inverse of vertex identification.
Path contraction is performed on a set of edges in a path, which are contracted, forming a single edge between the endpoints of the path. The edges incident to the vertices along the path are either removed or, randomly (or by some system), connected to one of the endpoints.
Suppose we are given two disjoint graphs G1 and G2, where G1 contains vertices u1 and v1, and G2 contains vertices u2 and v2. Suppose we have obtained a graph G by identifying the vertices u1 of graph G1 and u2 of graph G2, obtaining vertex u in G, and identifying the vertices v1 of graph G1 and v2 of graph G2, obtaining vertex v in G. In the twisting G' of graph G with respect to the pair of vertices {u, v}, we instead identify the vertices u1 with v2 and v1 with u2 .
Both edge contraction and vertex contraction are important for proofs by mathematical induction on the number of vertices or edges of a graph, where one can assume that a property holds for all smaller graphs and this can be used to prove properties of larger graphs.
Edge contraction is used in the recursive formula for the number of spanning trees of a random connected graph and in the recurrence formula for the chromatic polynomial of a simple graph .
Contraction is also useful in structures where we wish to simplify a graph by identifying vertices that represent essentially equivalent objects. The best-known example is the reduction of a general directed graph to a directed acyclic graph by contracting all vertices in each strongly connected component. If the relation described by the graph is transitive, no information is lost if each vertex is labeled with the set of labels of the vertices that were contracted into that vertex.
Another example — is the merging carried out in graph coloring during global register allocation, where vertices are merged (where possible) to eliminate data-movement operations between different variables.
Edge contraction is used in three-dimensional modeling packages (either manually or with the help of modeling programs) to progressively reduce the number of vertices in order to create models in the form of polygons with a small number of sides.
Comments