|
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
donde w sería el vértice resultante de la contracción de la arista uv, y x representa a los vértices en la vecindad de u y de v Véase tambiénReferencias
|
