Contracción de aristas

En el campo matemático de la teoría de grafos, una contracción de aristas también llamada contracción de grafos o simplemente contracción es una operación que elimina una arista del grafo al mismo tiempo que fusiona los dos vértices extremos. La contracción es una operación fundamental en la teoría de grafos.

La operación de contracción de aristas toma una arista e = uv, la cual es removida del grafo y los dos vértices incidentes u y v son fusionados en un nuevo vértice w, de modo tal que las aristas incidentes a w son las aristas incidentes de u y v

Más generalmente, la operación de contracción se puede dar sobre un conjunto de aristas en cualquier orden. Las contracciones de aristas pueden resultar en multigrafos con bucles o aristas múltiples, los que a veces se eliminan con el fin de mantenerse dentro de la clase de grafos simples.

La contracción de vértices es otra variante de la operación resta.

Definición formal

Sea $G(V,A)\,$ un grafo simple conexo, la contracción de la arista $\{u,v\}\in A\,$ da como resultado el grafo $C_{w}(G)(V',A')\,$ , donde $V'=V-\{u,v\}\cup \{w\}\,$ y $A'=A-\{\{x,u\},\{x,v\}:x\in V\}\cup \{\{x,w\}:x\in V,\{x,u\}\in A\lor \{x,v\}\in A\}\,$ ^[1]