suma de camarilla
En la teoría de grafos , una rama de las matemáticas, una suma clique es una forma de combinar dos gráficos pegándolos juntos en una camarilla , análoga a la operación de suma conectada en topología . Si dos gráficos, G y H , contienen cliques de igual tamaño, la suma 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 solo clique compartido, y luego posiblemente eliminando algunos de los bordes de camarilla. Una k -clique-sum es una clique-sum en la que ambas cliques tienen como máximo kvértices. También se pueden formar clique-sums y k -clique-sums de más de dos gráficos, mediante la aplicación repetida de la operación clique-sum de dos gráficos.
Diferentes fuentes no están de acuerdo sobre qué bordes deben eliminarse como parte de una operación de suma de camarilla. En algunos contextos, como la descomposición de grafos cordales o grafos estrangulados , no se deben eliminar bordes. En otros contextos, como la descomposición en árbol SPQR de gráficos en sus componentes conectados por 3 vértices, se deben eliminar todos los bordes. Y en otros contextos, como el teorema de la 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 camarilla tienen una conexión cercana con el ancho de árbol : si dos gráficos tienen un ancho de árbol como máximo k , también lo tiene su k -clique-sum. Cada árbol es la suma de 1 camarilla de sus bordes. Cada gráfico de 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 clicas de triángulos. El mismo tipo de resultado se extiende a valores más grandes de k : cada gráfico con ancho de árbol como máximo k puede formarse como una suma de camarilla de gráficos con como máximo k + 1 vértices; esto es necesariamente una k -clique-sum. [1]
También existe una estrecha conexión entre las sumas de clique y la conectividad de grafos : si un grafo no está conectado a ( k + 1) vértices (de modo que existe un conjunto de k vértices cuya eliminación desconecta el grafo), entonces puede ser representado como una k -clique-sum 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 clicas de sus componentes triconectados .
Las sumas de camarilla son importantes en la teoría de la estructura de gráficos, donde se utilizan para caracterizar ciertas familias de gráficos como los gráficos formados por sumas de camarilla de gráficos más simples. El primer resultado de este tipo [2] fue un teorema de Wagner (1937) , quien probó que los grafos que no tienen como menor un grafo completo de cinco vértices son las 3-clique-sumas de grafos planos con los 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 grafos cordalesson exactamente los gráficos que se pueden formar con sumas de camarillas de camarillas sin borrar ningún borde, y los gráficos estrangulados son los gráficos que se pueden formar con sumas de camarillas de camarillas y gráficos planares máximos sin borrar bordes. [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 , de nuevo sin supresiones de borde. [4] Johnson y McKee (1996)use las sumas de camarilla de grafos cordales y grafos serie-paralelo para caracterizar las matrices parciales que tienen terminaciones definidas positivas .
