En teoría de grafos , una rama de las matemáticas, una suma camarilla (o suma camarilla ) es una forma de combinar dos gráficos pegándolos en una camarilla , análoga a la operación de suma conectada en topología . Si dos gráficos G y H contienen camarillas de igual tamaño, la suma de camarillas de G y H se forma a partir de su unión disjunta identificando pares de vértices en estas dos camarillas para formar una única camarilla compartida y luego eliminando todos los bordes de la camarilla. (la definición original, basada en la noción de suma fija) o posiblemente eliminar algunos de los bordes de la camarilla (una relajación de la definición). Una k -clique-sum es una clique-sum en la que ambas camarillas tienen exactamente (o a veces, como máximo) k vértices. También se pueden formar sumas de camarilla y k -sumas de camarilla de más de dos gráficos, mediante la aplicación repetida de la operación de suma de camarilla.
Diferentes fuentes no están de acuerdo sobre qué bordes deben eliminarse como parte de una operación de suma de camarillas. En algunos contextos, como la descomposición de grafos cordales o grafos estrangulados , no se deben eliminar aristas. En otros contextos, como la descomposición de gráficos en árbol SPQR en sus componentes conectados por 3 vértices, se deben eliminar todos los bordes. Y en otros contextos más, como el teorema de estructura de grafos para familias menores cerradas de grafos simples, es natural permitir que el conjunto de aristas eliminadas se especifique como parte de la operación.
Las sumas de camarilla tienen una estrecha conexión con el ancho del árbol : si dos gráficos tienen un ancho de árbol como máximo k , también lo tiene su k -suma de camarilla. Cada árbol es la suma 1-clique de sus aristas. Cada gráfico en serie-paralelo , o más generalmente, cada gráfico con un ancho de árbol como máximo dos, puede formarse como una suma de 2 círculos de triángulos. El mismo tipo de resultado se extiende a valores más grandes de k : cada gráfico con un ancho de árbol como máximo k puede formarse como una suma de gráficos con un máximo de k + 1 vértices; esto es necesariamente una k -clique-sum. [1]
También existe una estrecha conexión entre las sumas de camarillas y la conectividad del gráfico : si un gráfico no está conectado a ( k + 1) vértices (de modo que existe un conjunto de k vértices cuya eliminación desconecta el gráfico), entonces puede ser representado como una k -clique-suma de gráficos más pequeños. Por ejemplo, el árbol SPQR de un gráfico biconectado es una representación del gráfico como una suma de 2 camarillas de sus componentes triconectados .
Las sumas de camarillas son importantes en la teoría de la estructura de grafos, donde se utilizan para caracterizar ciertas familias de gráficos como los gráficos formados por sumas de camarillas de gráficos más simples. El primer resultado de este tipo [2] fue un teorema de Wagner (1937), quien demostró que las gráficas que no tienen una gráfica completa de cinco vértices como menor son las sumas de 3 clics de gráficas planas con ocho vértices. Gráfico de Wagner de vértice ; este teorema de estructura se puede utilizar para demostrar que el teorema de los cuatro colores es equivalente al caso k = 5 de la conjetura de Hadwiger . Los gráficos cordales son exactamente los gráficos que pueden formarse mediante sumas de camarillas de camarillas sin eliminar ningún borde, y los gráficos estrangulados son los gráficos que pueden formarse mediante sumas de camarillas de camarillas y gráficos planos máximos sin eliminar aristas. [3] Los gráficos en los que cada ciclo inducido de longitud cuatro o más forma un separador mínimo del gráfico (su eliminación divide el gráfico en dos o más componentes desconectados, y ningún subconjunto del ciclo tiene la misma propiedad) son exactamente la camarilla -sumas de camarillas y gráficos planos máximos , nuevamente sin eliminaciones de bordes. [4] Johnson y McKee (1996) utilizan las sumas de camarillas de gráficos cordales y gráficos de series-paralelas para caracterizar las matrices parciales que tienen terminaciones definidas positivas .
Es posible derivar una descomposición de suma de camarillas para cualquier familia de gráficos cerrada bajo operaciones menores de gráficas: las gráficas de cada familia cerrada menor pueden formarse a partir de sumas de camarillas de gráficos que están "casi incrustados" en superficies de género acotado , es decir que la incrustación puede omitir una pequeña cantidad de vértices (vértices que pueden estar conectados a un subconjunto arbitrario de los otros vértices) y vórtices (gráficos con ancho de ruta bajo que reemplazan las caras de la incrustación de la superficie). [5] Estas caracterizaciones se han utilizado como una herramienta importante en la construcción de algoritmos de aproximación y algoritmos exactos de tiempo subexponencial para problemas de optimización NP-completos en familias de gráficos menores cerrados. [6]
La teoría de las sumas de camarillas también se puede generalizar desde gráficos hasta matroides . [1] En particular, el teorema de descomposición de Seymour caracteriza las matroides regulares (las matroides representables por matrices totalmente unimodulares ) como las 3 sumas de matroides gráficas (las matroides que representan árboles de expansión en un gráfico), matroides cográficas y una determinada matroide de 10 elementos. . [1] [7]