Contracción de aristas

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
La arista uv se contrae en el punto w

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 un 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[editar]

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 \or \{x,v\} \in A \} \,[1]

donde w seria 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én[editar]

Referencias[editar]