En la teoría de grafos , una rama de las matemáticas, un clique-sum es una forma de combinar dos gráficos pegándolos juntos en un clique , análogo a la operación de suma conectada en topología . Si dos gráficos 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 solo clique compartido, y luego posiblemente eliminando algunos de los bordes de la camarilla. Una k -clique-sum es una clique-suma en la que ambas camarillas tienen como máximo kvértices. También se pueden formar sumas de clique y k sumas de clique de más de dos gráficos, mediante la aplicación repetida de la operación de suma de clique 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 camarillas. En algunos contextos, como la descomposición de grafos cordales o grafos estrangulados , no se deben eliminar los bordes. 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, 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.
Conceptos relacionados
Las sumas de clique tienen una estrecha conexión 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 una camarilla de sus bordes. 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 triángulos de 2 clique. 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 un clique-suma de gráficos con un máximo de k + 1 vértices; esto es necesariamente una k -clique-sum. [1]
También hay una estrecha conexión entre las sumas de clique y la conectividad del gráfico : si un gráfico no está ( k + 1) conectado al vértice (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 clique de sus componentes triconectados .
Aplicación en la teoría de la estructura de grafos
Las sumas de clique 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 clique 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 clique de gráficas planas con ocho 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 los bordes. [3] Los gráficos en los que cada ciclo inducido de cuatro o más de longitud 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 pandilla -sumas de camarillas y gráficos planos máximos , nuevamente sin eliminaciones de bordes. [4] Johnson y McKee (1996) utilizan las sumas de clique de los gráficos cordales y los gráficos de series paralelas para caracterizar las matrices parciales que tienen terminaciones definidas positivas .
Es posible derivar una descomposición de suma de clique para cualquier familia de gráficos cerrada bajo operaciones menores de gráfico: los gráficos en cada familia cerrada de menor importancia pueden formarse a partir de sumas de clique de gráficos que están "casi incrustados" en superficies de género acotado , lo que significa que a la incrustación se le permite 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 un ancho de trayectoria bajo que reemplazan las caras de la incrustación de superficie). [5] Estas caracterizaciones se han utilizado como una herramienta importante en la construcción de algoritmos de aproximación y algoritmos exactos subexponenciales en tiempo para problemas de optimización NP-completa en familias de grafos cerrados menores. [6]
Generalizaciones
La teoría de las sumas de camarillas también se puede generalizar de gráficos 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 gráfico), matroides cográficas y una determinada matroide de 10 elementos. . [1] [7]
Notas
- ↑ a b c Lovász (2006) .
- ^ Según lo acreditan Kříž & Thomas (1990) , quienes enumeran varias caracterizaciones adicionales de familias de gráficos basadas en la suma de clique.
- ^ Seymour y Weaver (1984) .
- ^ Diestel (1987) .
- ^ Robertson y Seymour (2003)
- ^ Demaine y col. (2004) ; Demaine y col. (2005) ; Demaine, Hajiaghayi y Kawarabayashi (2005) .
- ^ Seymour (1980) .
Referencias
- Demaine, Erik D .; Fomin, Fedor V .; Hajiaghayi, MohammedTaghi; Thilikos, Dimitrios (2005), "Algoritmos parametrizados subexponenciales en gráficos de género acotado y gráficos libres de H -minor", Journal of the ACM , 52 (6): 866–893, arXiv : 1104.2230 , doi : 10.1145 / 1101821.1101823 , MR 2179550.
- Demaine, Erik D .; Hajiaghayi, MohammedTaghi; Nishimura, Naomi; Ragde, Prabhakar; Thilikos, Dimitrios (2004), "Algoritmos de aproximación para clases de gráficos que excluyen los gráficos de un solo cruce como menores", Journal of Computer and System Sciences , 69 (2): 166-195, doi : 10.1016 / j.jcss.2003.12.001 , MR 2077379.
- Demaine, Erik D .; Hajiaghayi, MohammedTaghi; Kawarabayashi, Ken-ichi (2005), "Teoría menor de grafos algorítmicos: descomposición, aproximación y coloración" (PDF) , Actas del 46º Simposio IEEE sobre Fundamentos de la informática (PDF) , págs. 637–646, doi : 10.1109 /SFCS.2005.14.
- Diestel, Reinhard (1987), "Una propiedad de separación de triangulaciones planas", Journal of Graph Theory , 11 (1): 43–52, doi : 10.1002 / jgt.3190110108 , MR 0876203.
- Kříž, Igor; Thomas, Robin (1990), "Clique-sums, tree-descompositions and compactness", Discrete Mathematics , 81 (2): 177-185, doi : 10.1016 / 0012-365X (90) 90150-G , MR 1054976.
- Johnson, Charles R .; McKee, Terry A. (1996), "Condiciones estructurales para gráficos de ciclo completo", Matemáticas discretas , 159 (1-3): 155-160, doi : 10.1016 / 0012-365X (95) 00107-8 , MR 1415290.
- Lovász, László (2006), "Graph minor theory", Bulletin of the American Mathematical Society , 43 (1): 75–86, doi : 10.1090 / S0273-0979-05-01088-8 , MR 2188176.
- Robertson, N .; Seymour, PD (2003), "Graph minors XVI. Excluyendo un gráfico no plano", Journal of Combinatorial Theory , Serie B, 89 (1): 43–76, doi : 10.1016 / S0095-8956 (03) 00042-X , Señor 1999736.
- Seymour, PD (1980), "Decomposition of regular matroids", Journal of Combinatorial Theory , Serie B, 28 (3): 305–359, doi : 10.1016 / 0095-8956 (80) 90075-1 , MR 0579077.
- Seymour, PD ; Weaver, RW (1984), "A generalization of chordal graphs", Journal of Graph Theory , 8 (2): 241-251, doi : 10.1002 / jgt.3190080206 , MR 0742878.
- Wagner, Klaus (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen , 114 : 570–590, doi : 10.1007 / BF01594196.