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{ oder }}\{v,x\}{\mbox{ Kante von 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}}$