En teoría de grafos , una contracción de aristas es una operación que elimina una arista de un gráfico y al mismo tiempo fusiona los dos vértices que unía previamente. La contracción de aristas 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.
La operación de contracción del borde se produce en relación con un borde particular . La arista se elimina y sus dos vértices incidentes, y , se fusionan en un nuevo vértice , donde las aristas incidentes en cada uno corresponden a una arista incidente en o . De manera más general, la operación se puede realizar en un conjunto de bordes contrayendo cada borde (en cualquier orden). [1]
El gráfico resultante a veces se escribe como . (Compárese con , que significa eliminar el borde ).
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, de modo que las contracciones de aristas realizadas en gráficos simples siempre producen gráficos simples.
Sea un gráfico ( o gráfico dirigido ) que contenga una arista con . Sea una función que asigna cada vértice a sí misma y, de lo contrario, lo asigna 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 en .
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 del gráfico. A veces se eliminan los bordes entre dos vértices que se contraen . Si y son vértices de componentes distintos de , entonces podemos crear un nuevo gráfico identificando y en como un nuevo vértice en . [4] De manera más general, dada una partición del conjunto de vértices, se pueden identificar los vértices en la partición; la gráfica resultante se conoce como gráfica de cociente .
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 era adyacente el vértice original. Esta es una operación inversa a la 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.
La contracción del camino ocurre en el conjunto de bordes de un camino que se contraen para formar un solo borde entre los puntos finales del camino. Los bordes incidentes a los vértices a lo largo del camino se eliminan o se conectan arbitrariamente (o sistemáticamente) a uno de los puntos finales.
Considere dos gráficos disjuntos y , donde contiene vértices y y contiene vértices y . Supongamos que podemos obtener la gráfica identificando los vértices de y de como el vértice de e identificando los vértices de y de como el vértice de . En una torsión de con respecto al conjunto de vértices , nos identificamos, en cambio, con y con . [5]
Tanto las técnicas de contracción de aristas como de vértices son valiosas en la prueba por inducción del número de vértices o aristas en un gráfico, donde se puede suponer que una propiedad se cumple para todos los gráficos más pequeños y esto se puede usar para probar la propiedad para el gráfico más grande.
La contracción de bordes se utiliza en la fórmula recursiva para el número de árboles generadores 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 gráfico dirigido general a un gráfico dirigido acíclico contrayendo todos los vértices en cada componente fuertemente conectado . Si la relación que describe 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 gráficos 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 constantemente el número de vértices, lo que ayuda en la creación de modelos con pocos polígonos.
