Contracción del borde

Contrayendo el borde entre los vértices indicados, dando como resultado el gráfico G / {uv}.

En teoría de grafos , una contracción de aristas es una operación que elimina una arista de un grafo mientras simultáneamente fusiona los dos vértices que unió previamente. La contracción del borde es una operación fundamental en la teoría de grafos menores . La identificación de vértices es una forma menos restrictiva de esta operación.

Definición

La contracción borde operación se produce con relación a un borde particular . El borde se elimina y sus dos vértices incidentes y , se fusionan en un nuevo vértice , donde los bordes incidentes a cada uno corresponden a un borde incidente a o . De manera más general, la operación se puede realizar en un conjunto de bordes contrayendo cada borde (en cualquier orden). ^[1]${\displaystyle e}$${\displaystyle e}$${\displaystyle u}$${\displaystyle v}$${\displaystyle w}$${\displaystyle w}$${\displaystyle u}$${\displaystyle v}$

El gráfico inducido resultante a veces se escribe como . (Compare esto con , lo que significa quitar el borde ). ${\displaystyle G/e}$${\displaystyle G\setminus e}$${\displaystyle e}$

Contracción de un borde sin crear múltiples bordes.

Como se define a continuación, una operación de contracción de bordes puede dar como resultado un gráfico con múltiples bordes incluso si el gráfico original era un gráfico simple . ^[2] Sin embargo, algunos autores ^[3] no permiten la creación de múltiples aristas, por lo que las contracciones de aristas realizadas en gráficos simples siempre producen gráficos simples.

Definicion formal

Sea un gráfico ( o gráfico dirigido ) que contiene una arista con . Sea una función que mapee cada vértice en sí mismo y, de lo contrario, lo mapee a un nuevo vértice . La contracción de da como resultado un nuevo gráfico , donde , y para cada , es incidente a un borde si y solo si, el borde correspondiente, es incidente a in .${\displaystyle G=(V,E)}$${\displaystyle e=(u,v)}$${\displaystyle u\neq v}$${\displaystyle f}$${\displaystyle V\setminus \{u,v\}}$${\displaystyle w}$${\displaystyle e}$${\displaystyle G'=(V',E')}$${\displaystyle V'=(V\setminus \{u,v\})\cup \{w\}}$${\displaystyle E'=E\setminus \{e\}}$${\displaystyle x\in V}$${\displaystyle x'=F(x)\in V'}$${\displaystyle e'\in E'}$${\displaystyle e\in E}$${\displaystyle x}$${\displaystyle G}$

Identificación de vértices

La identificación de vértices (a veces llamada contracción de vértices ) elimina la restricción de que la contracción debe ocurrir sobre vértices que comparten un borde incidente. (Por lo tanto, la contracción de aristas es un caso especial de identificación de vértices). La operación puede ocurrir en cualquier par (o subconjunto) de vértices en el gráfico. A veces se eliminan los bordes entre dos vértices que se contraen . Si y son vértices de componentes distintos de , a continuación, podemos crear un nuevo gráfico mediante la identificación y en como un nuevo vértice en . ^[4] De manera más general, dada una partición${\displaystyle v}$${\displaystyle v'}$${\displaystyle G}$${\displaystyle G'}$${\displaystyle v}$${\displaystyle v'}$${\displaystyle G}$${\displaystyle {\textbf {v}}}$${\displaystyle G'}$del conjunto de vértices, se pueden identificar vértices en la partición; el gráfico resultante se conoce como gráfico de cociente .

Corte de vértice

La división de vértices , que es lo mismo que la división de vértices, significa que un vértice se divide en dos, donde estos dos nuevos vértices son adyacentes a los vértices a los que estaba adyacente el vértice original. Esta es una operación inversa de identificación de vértices, aunque en general para la identificación de vértices, los vértices adyacentes de los dos vértices identificados no son el mismo conjunto.

Contracción del camino

La contracción de la trayectoria se produce sobre el conjunto de bordes de una trayectoria que se contraen para formar un solo borde entre los puntos finales de la trayectoria. Los bordes incidentes con los vértices a lo largo del camino se eliminan o se conectan arbitrariamente (o sistemáticamente) a uno de los puntos finales.

Retortijón

Considere dos gráficos disjuntos y , donde contiene vértices y y contiene vértices y . Suponga que podemos obtener la gráfica identificando los vértices de y de como vértice de e identificando los vértices de y de como vértice de . En una torsión de con respecto al conjunto de vértices , identificamos, en cambio, con y con . ^[5]${\displaystyle G_{1}}$${\displaystyle G_{2}}$${\displaystyle G_{1}}$${\displaystyle u_{1}}$${\displaystyle v_{1}}$${\displaystyle G_{2}}$${\displaystyle u_{2}}$${\displaystyle v_{2}}$${\displaystyle G}$${\displaystyle u_{1}}$${\displaystyle G_{1}}$${\displaystyle u_{2}}$${\displaystyle G_{2}}$${\displaystyle u}$${\displaystyle G}$${\displaystyle v_{1}}$${\displaystyle G_{1}}$${\displaystyle v_{2}}$${\displaystyle G_{2}}$${\displaystyle v}$${\displaystyle G}$ ${\displaystyle G'}$${\displaystyle G}$${\displaystyle \{u,v\}}$${\displaystyle u_{1}}$${\displaystyle v_{2}}$${\displaystyle v_{1}}$${\displaystyle u_{2}}$

Aplicaciones

Tanto las técnicas de contracción de aristas como de vértices son valiosas en la demostración por inducción sobre el número de vértices o aristas en un gráfico, donde se puede suponer que una propiedad es válida para todos los gráficos más pequeños y esto puede usarse para probar la propiedad para el gráfico más grande.

La contracción de aristas se usa en la fórmula recursiva para el número de árboles de expansión de un gráfico conectado arbitrario , ^[6] y en la fórmula de recurrencia para el polinomio cromático de un gráfico simple. ^[7]

Las contracciones también son útiles en estructuras donde deseamos simplificar un gráfico identificando vértices que representan entidades esencialmente equivalentes. Uno de los ejemplos más comunes es la reducción de un grafo dirigido general a un grafo dirigido acíclico al contraer todos los vértices en cada componente fuertemente conectado . Si la relación descrita por el gráfico es transitiva , no se pierde información siempre que etiquetemos cada vértice con el conjunto de etiquetas de los vértices que se contrajeron para formarlo.

Otro ejemplo es la fusión realizada en la asignación de registros de coloración de grafos globales , donde los vértices se contraen (donde es seguro) para eliminar operaciones de movimiento entre distintas variables.

La contracción de bordes se utiliza en paquetes de modelado 3D (ya sea manualmente o mediante alguna función del software de modelado) para reducir consistentemente el recuento de vértices, ayudando en la creación de modelos de polígono bajo.

Ver también

• Subdivisión (teoría de grafos)

Notas

1. Gross y Yellen 1998 , p. 264
2. Además,pueden surgir bucles cuando el gráfico comienza con varios bordes o, incluso si el gráfico es simple, a partir de la aplicación repetida de la contracción del borde.
3. Rosen , 2011 , p. 664
4. Oxley 1992 , págs. 147-148
5. Oxley 1992 , p. 148
6. Gross y Yellen 1998 , p. 264
7. West 2001 , p. 221

Referencias

• Gross, Jonathan; Yellen, Jay (1998), Graph Theory y sus aplicaciones , CRC Press, ISBN 0-8493-3982-0
• Oxley, James (1992), teoría de la matriz , Oxford University Press
• Rosen, Kenneth (2011), Matemáticas discretas y sus aplicaciones (7a ed.), McGraw-Hill, ISBN 9780073383095
• West, Douglas B. (2001), Introducción a la teoría de grafos (2a ed.), Prentice-Hall, ISBN 0-13-014400-2

enlaces externos

• Weisstein, Eric W. "Edge Contraction" . MathWorld .