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 operación de contracción del borde ocurre 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 inciden cada uno corresponde a un incidente de borde a cualquiera 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 inducido resultante a veces se escribe como . (Compare esto con, lo que significa quitar 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, por lo que las contracciones de aristas realizadas en gráficos simples siempre producen gráficos simples.
Definicion formal
Dejar ser un gráfico ( o gráfico dirigido ) que contiene un borde con . Dejar ser una función que mapea cada vértice en a sí mismo, y de lo contrario, lo mapea a un nuevo vértice . La contracción de da como resultado un nuevo gráfico , dónde , y por cada , es incidente a un borde si y solo si, el borde correspondiente, es incidente a en .
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 distintos componentes de , luego 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 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 inconexos y , dónde 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 , identificamos, en cambio, con y con . [5]
Aplicaciones
Ambas técnicas de contracción de aristas y 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 se puede usar para probar la propiedad para el gráfico más grande.
La contracción de aristas se utiliza 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 constantemente el recuento de vértices, lo que ayuda a crear modelos de polígono bajo.
Ver también
Notas
- ^ Gross y Yellen 1998 , p. 264
- ^ 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.
- ↑ Rosen , 2011 , p. 664
- ^ Oxley 1992 , págs. 147-148
- ^ Oxley 1992 , p. 148
- ^ Gross y Yellen 1998 , p. 264
- ^ 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