En teoría de grafos , una rama de las matemáticas, una suma de clique (o suma de clique ) es una forma de combinar dos grafos pegándolos juntos en una clique , análoga a la operación de suma conexa en topología . Si dos grafos G y H contienen cada uno cliques de igual tamaño, la suma de clique de G y H se forma a partir de su unión disjunta identificando pares de vértices en estos dos cliques para formar un único clique compartido, y luego eliminando todos los bordes de clique (la definición original, basada en la noción de suma de conjuntos) o posiblemente eliminando algunos de los bordes de clique (una flexibilización de la definición). Una suma de clique k es una suma de clique en la que ambos cliques tienen exactamente (o a veces, como máximo) k vértices. También se pueden formar sumas de clique y sumas de clique k de más de dos grafos, mediante la aplicación repetida de la operación de suma de clique.
Diferentes fuentes no están de acuerdo sobre qué aristas se deben eliminar como parte de una operación de suma de clique. En algunos contextos, como la descomposición de grafos cordales o grafos estrangulados , no se debe eliminar ninguna arista. En otros contextos, como la descomposición de grafos en árboles SPQR en sus componentes conectados por 3 vértices, se deben eliminar todas las aristas. Y en otros contextos, como el teorema de estructura de grafos para familias cerradas menores de grafos simples, es natural permitir que el conjunto de aristas eliminadas se especifique como parte de la operación.
Las sumas de clique tienen una estrecha relación con el ancho de árbol : si dos grafos tienen un ancho de árbol de k como máximo , también lo tiene su suma de k -clique. Todo árbol es la suma de 1-clique de sus aristas. Todo grafo serie-paralelo , o más generalmente todo grafo con un ancho de árbol de dos como máximo, puede formarse como una suma de 2-clique de triángulos. El mismo tipo de resultado se extiende a valores mayores de k : todo grafo con un ancho de árbol de k como máximo puede formarse como una suma de clique de grafos con como máximo k + 1 vértices; esto es necesariamente una suma de k -clique. [1]
También existe una estrecha conexión entre las sumas de clique y la conectividad de grafos : si un grafo no está ( k + 1)-conexo por vértices (de modo que existe un conjunto de k vértices cuya eliminación desconecta el grafo), entonces puede representarse como una suma de k -clique de grafos más pequeños. Por ejemplo, el árbol SPQR de un grafo biconexo es una representación del grafo como una suma de 2-clique de sus componentes triconexos .
Las sumas de clique son importantes en la teoría de la estructura de grafos, donde se utilizan para caracterizar ciertas familias de grafos como los grafos formados por sumas de clique de grafos más simples. El primer resultado de este tipo [2] fue un teorema de Wagner (1937), quien demostró que los grafos que no tienen un grafo completo de cinco vértices como menor son las sumas de 3 clique de grafos planares con el grafo de Wagner de ocho vértices ; este teorema de estructura se puede utilizar para mostrar que el teorema de los cuatro colores es equivalente al caso k = 5 de la conjetura de Hadwiger . Los grafos cordales son exactamente los grafos que se pueden formar por sumas de clique de cliques sin eliminar ninguna arista, y los grafos estrangulados son los grafos que se pueden formar por sumas de clique de cliques y grafos planares maximalistas sin eliminar aristas. [3] Los grafos en los que cada ciclo inducido de longitud cuatro o mayor forma un separador mínimo del grafo (su eliminación divide el grafo en dos o más componentes desconectados, y ningún subconjunto del ciclo tiene la misma propiedad) son exactamente las sumas de camarillas de camarillas y grafos planares maximos , nuevamente sin eliminaciones de aristas. [4] Johnson y McKee (1996) utilizan las sumas de camarillas de grafos cordales y grafos serie-paralelos para caracterizar las matrices parciales que tienen terminaciones definidas positivas .
Es posible derivar una descomposición en suma de camarillas para cualquier familia de grafos cerrada bajo operaciones de grafos menores: los grafos en cada familia cerrada de menores pueden formarse a partir de sumas de camarillas de grafos que están "casi incrustados" en superficies de género acotado , lo que significa que se permite que la incrustación omita 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 (grafos con ancho de camino bajo que reemplazan 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 grafos cerrados de menores. [6]
La teoría de sumas de clique también puede generalizarse desde grafos a matroides . [1] En particular, el teorema de descomposición de Seymour caracteriza a 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 grafo), matroides cográficas y un cierto matroide de 10 elementos. [1] [7]