En teoría de grafos , una contracción de aristas es una operación en un grafo. Consiste pictóricamente en contraer un borde de un gráfico, lo que equivale a fusionar sus dos extremos.
Esta operación es fundamental para la teoría de los mineros de grafos y se utiliza en algunos algoritmos y algunas pruebas.
Sea una gráfica G = (V, E) , que contiene una arista (u, v) , con u diferente de v . La contracción de (u, v) es la operación que consiste en la transformación de G en un gráfico G '= (V', E ') , donde V' es igual a V excepto que u y v se sustituyen por un vértice único w , y E ' es igual a E excepto que las apariciones de u y v se reemplazan por w .
Dependiendo del campo de aplicación, se eliminan o no los bucles y pliegues múltiples creados por la contracción.
El algoritmo de Karger para el corte mínimo y el algoritmo de Borůvka para el árbol de expansión de peso mínimo utilizan la contracción del borde.