Subdivisión (grafos)

En el campo matemático de la teoría de grafos, una subdivisión de aristas también llamada subdivisión elemental, subdivisión de grafos​ o simplemente subdivisión es una operación que agrega un vértice a una arista, dividiendo la arista en dos (•——• por •—•—•). La contracción es una operación fundamental en la teoría de grafos.

Subdivisión

subdivisión de la arista uv en las aristas uw y wv

La operación de subdivisión de aristas toma una arista e = uv, luego un vértice w es agregado a la arista, dividiéndola en dos, de esta forma la arista original es reemplazada por e₁ = uw y e₂ = wv, de modo que se añade al grafo un vértice y una arista.

Más generalmente, la operación de subdivisión puede añadir un conjunto de vértices a una arista, dividiendo la arista y añadiendo un grafo camino P_n al grafo. La subdivisión se puede realizar en más de una arista a la vez.

Definición formal

Sea $G(V,A)\,$ un grafo simple conexo, la subdivisión de la arista $\{u,v\}\in A\,$ da como resultado el grafo $G_{w}(V',A')\,$, donde $V'=V\cup \{w\}\,$ y $A'=(A-\{u,v\})\cup \{\{u,w\},\{v,w\}\}\,$​

donde w sería el vértice que se inserta en la arista.

Operación inversa

La operación inversa, suavizado o alisado de un grafo, un vértice w es eliminado de un par de aristas (e,f) que son incidentes a w, se elimina las aristas incidentes a w y se reemplaza por una nueva arista con los vértices extremos de e y f que no son w. Esta operación se puede hacer únicamente con vértices de grado 2.

Por ejemplo, el grafo G simple conexo con dos aristas e₁ = uw y e₂ = wv:

tiene un vértice w que es alisado, resultando:

Véase también

• Homeomorfismo de grafos
• Anexo:Operaciones en grafos

Referencias

• Datos: Q6134791