Edge contraction

In graph theory, edge contraction or contraction refers to a fundamental operation on graphs. In this case, an edge e is removed and the two adjacent nodes are combined to form a new node w.

Definition

An undirected graph, an edge from w, and a node not heard. Define as the set of edges between the remaining nodes of the graph and the node being removed that are redirected to the new node, so

• If a graph without multiple edges,

Or

• For all and for all, if a graph with multiple edges.

It is said that the graph is produced by contraction of e to w if. There are so removed from the node and all participating edges, and then added the new node and the deflected edges. The graph is a minor of the graph.

• Basic concept (graph theory )