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[1] 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 un 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 e1 = uw y e2 = 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 Pn al grafo. La subdivisión se puede realizar en más de una arista a la vez.

Definición formal

Sea un grafo simple conexo, la subdivisión de la arista da como resultado el grafo , donde y [2]

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 e1 = uw y e2 = wv:

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

Véase también

Referencias

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.