Edge contraction

Example of an edge contraction with the graphs (left) and (right).${\ displaystyle G_ {1}}$${\ displaystyle G_ {2}}$

In graph theory , edge contraction or contraction denotes a basic operation on graphs . An edge e is removed and the two adjacent nodes are combined to form a new node w .

definition

Let be an undirected graph, an edge of and w a vertex that does not belong to . Define as the set of edges between the remaining nodes of the graph and the nodes to be removed that are redirected to the new node, i.e. ${\ displaystyle G_ {1} = (V_ {1}, E_ {1})}$${\ displaystyle e = \ {u, v \}}$${\ displaystyle G_ {1}}$${\ displaystyle V_ {1}}$${\ displaystyle E}$${\ displaystyle \ {u, v \}}$${\ displaystyle w}$

• ${\ displaystyle E = {\ bigg \ {} \ {w, x \} {\ bigg |} \ forall _ {x \ in V_ {1} \ setminus \ {u, v \}} \ {u, x \ } {\ mbox {or}} \ {v, x \} {\ mbox {edge of G}} {\ bigg \}}}$if there is a graph without multiple edges,${\ displaystyle G_ {1}}$

or.

• ${\ displaystyle E (\ {w, x \}) = E_ {1} (\ {u, x \}) + E_ {1} (\ {v, x \})}$for all and for all if is a graph with multiple edges.${\ displaystyle x \ in V_ {1} \ {u, v \}}$${\ displaystyle E (\ {x, y \}) = 0}$${\ displaystyle x, y \ in V_ {1} \ {u, v \}}$${\ displaystyle G_ {1}}$

It is said that the graph comes from by contraction of e to w if . The nodes and all involved edges are removed from, and then the new node and the deflected edges are added. The graph is a minor of the graph . ${\ displaystyle G_ {2} = (V_ {2}, E_ {2})}$${\ displaystyle G_ {1}}$${\ displaystyle G_ {2} = G_ {1} - \ {u, v \} + w + E}$${\ displaystyle G_ {1}}$${\ displaystyle \ {u, v \}}$${\ displaystyle w}$${\ displaystyle G_ {2}}$${\ displaystyle G_ {1}}$