Camarilla (teoría de grafos)

En teoría de grafos , una camarilla ( / ˈ k l iː k / o / ˈ k l ɪ k / ) es un subconjunto de vértices de un grafo no dirigido tal que cada par de vértices distintos en la camarilla son adyacentes . Es decir, una camarilla de un grafo${\displaystyle G}$es un subgrafo inducido de${\displaystyle G}$Eso es completo . Las camarillas son uno de los conceptos básicos de la teoría de grafos y se utilizan en muchos otros problemas matemáticos y construcciones sobre grafos. Las camarillas también se han estudiado en informática : la tarea de determinar si existe una camarilla de un tamaño dado en un grafo (el problema de la camarilla ) es NP-completa , pero a pesar de esta dificultad, se han estudiado muchos algoritmos para encontrar camarillas.

Aunque el estudio de subgrafos completos se remonta al menos a la reformulación en teoría de grafos de la teoría de Ramsey por Erdős y Szekeres (1935) , ^{[ 1 ]} el término camarilla proviene de Luce y Perry (1949) , quienes utilizaron subgrafos completos en redes sociales para modelar camarillas de personas; es decir, grupos de personas que se conocen entre sí. Las camarillas tienen muchas otras aplicaciones en las ciencias y particularmente en bioinformática .

Una camarilla , C , en un grafo no dirigido G = ( V , E ) es un subconjunto de los vértices , C ⊆ V , tal que cada par de vértices distintos son adyacentes. Esto equivale a la condición de que el subgrafo inducido de G por C sea un grafo completo . En algunos casos, el término camarilla también puede referirse directamente al subgrafo.

Una camarilla maximal es una camarilla que no es un subconjunto de ninguna camarilla mayor. Algunos autores definen las camarillas exigiendo que sean maximalistas, y utilizan otra terminología para los subgrafos completos que no lo son.

Una camarilla máxima de un grafo G es una camarilla tal que no existe ninguna otra con más vértices. Además, el número de camarilla ω ( G ) de un grafo G es el número de vértices en una camarilla máxima en G.

El número de intersección de G es el número más pequeño de camarillas que juntas cubren todas las aristas de G.

El número de cobertura de cliques de un grafo G es el número más pequeño de cliques de G cuya unión cubre el conjunto de vértices V del grafo.

Una transversal de clique máxima de un grafo es un subconjunto de vértices con la propiedad de que cada clique máxima del grafo contiene al menos un vértice en el subconjunto. ^{[ 2 ]}

Lo opuesto a una camarilla es un conjunto independiente , en el sentido de que cada camarilla corresponde a un conjunto independiente en el grafo complemento . El problema de la cobertura de camarillas consiste en encontrar la menor cantidad posible de camarillas que incluyan todos los vértices del grafo.

Un concepto relacionado es el de biclique , un subgrafo bipartito completo . La dimensión bipartita de un grafo es el número mínimo de bicliques necesarios para cubrir todas las aristas del grafo.

Los resultados matemáticos relativos a las camarillas incluyen los siguientes.

• El teorema de Turán proporciona una cota inferior para el tamaño de una camarilla en grafos densos . ^{[ 3 ]} Si un grafo tiene suficientes aristas, debe contener una camarilla grande. Por ejemplo, todo grafo con${\displaystyle n}$vértices y más de${\displaystyle \scriptstyle \left\lfloor {\frac {n}{2}}\right\rfloor \cdot \left\lceil {\frac {n}{2}}\right\rceil }$Las aristas deben contener una camarilla de tres vértices.
• El teorema de Ramsey establece que todo grafo o su grafo complemento contiene una camarilla con al menos un número logarítmico de vértices. ^{[ 4 ]}
• Según un resultado de Moon y Moser (1965) , un grafo con 3n vértices puede tener como máximo 3n ^camarillas máximas. Los grafos que cumplen este límite son los grafos de Moon-Moser K3,3 _,... , un caso especial de los grafos de Turán que surgen como casos extremos en el teorema de Turán.
• La conjetura de Hadwiger , aún sin probar, relaciona el tamaño del clique menor más grande en un grafo (su número de Hadwiger ) con su número cromático .
• La conjetura de Erdős-Faber-Lovász relaciona la coloración de gráficos con camarillas.
• La conjetura de Erdős-Hajnal afirma que las familias de grafos definidas por una caracterización de grafos prohibida tienen grandes camarillas o grandes cocliques .

Varias clases importantes de grafos pueden definirse o caracterizarse por sus camarillas:

• Un grafo de clúster es un grafo cuyos componentes conectados son camarillas.
• Un grafo de bloques es un grafo cuyos componentes biconectados son camarillas.
• Un grafo cordal es un grafo cuyos vértices se pueden ordenar en un orden de eliminación perfecto, un ordenamiento tal que los vecinos de cada vértice v que aparecen después de v en el ordenamiento forman una camarilla.
• Un cografo es un grafo cuyos subgrafos inducidos tienen la propiedad de que cualquier clique maximal interseca cualquier conjunto independiente maximal en un solo vértice.
• Un grafo de intervalos es un grafo cuyos cliques máximos se pueden ordenar de tal manera que, para cada vértice v , los cliques que contienen a v son consecutivos en el ordenamiento.
• Un grafo de líneas es un grafo cuyas aristas pueden cubrirse mediante camarillas disjuntas en aristas, de tal manera que cada vértice pertenece exactamente a dos de las camarillas de la cobertura.
• Un grafo perfecto es un grafo en el que el número de clique es igual al número cromático en cada subgrafo inducido .
• Un grafo dividido es un grafo en el que alguna camarilla contiene al menos un extremo de cada arista.
• Un grafo libre de triángulos es un grafo que no tiene camarillas aparte de sus vértices y aristas.

Además, muchas otras construcciones matemáticas involucran camarillas en grafos. Entre ellas,

• El complejo de cliques de un grafo G es un complejo simplicial abstracto X ( G ) con un simplex para cada clique en G.
• Un grafo simplex es un grafo no dirigido κ( G ) con un vértice por cada clique en un grafo G y una arista que conecta dos cliques que difieren en un solo vértice. Es un ejemplo de grafo mediano y está asociado con un álgebra mediana sobre los cliques de un grafo: la mediana m ( A , B , C ) de tres cliques A , B y C es el clique ^cuyos vértices pertenecen al menos a dos de los cliques A , B y C. ^{[ 5} ]
• El método de suma de cliques consiste en combinar dos grafos fusionándolos a lo largo de un clique compartido.
• El ancho de clique es una medida de la complejidad de un grafo en términos del número mínimo de etiquetas de vértice distintas necesarias para construir el grafo a partir de uniones disjuntas, operaciones de reetiquetado y operaciones que conectan todos los pares de vértices con etiquetas dadas. Los grafos con ancho de clique igual a uno son precisamente las uniones disjuntas de cliques.
• El número de intersección de un grafo es el número mínimo de camarillas necesarias para cubrir todas las aristas del grafo.
• El grafo de camarillas de un grafo es el grafo de intersección de sus camarillas máximas.

Conceptos estrechamente relacionados con los subgrafos completos son las subdivisiones de grafos completos y los menores de grafos completos . En particular, el teorema de Kuratowski y el teorema de Wagner caracterizan los grafos planares mediante subdivisiones y menores completos y bipartitos prohibidos , respectivamente.

En ciencias de la computación , el problema de la camarilla es el problema computacional de encontrar una camarilla máxima, o todas las camarillas, en un grafo dado. Es NP-completo , uno de los 21 problemas NP-completos de Karp . ^{[ 6 ]} También es intratable con parámetros fijos y difícil de aproximar . Sin embargo, se han desarrollado muchos algoritmos para calcular camarillas, ya sea ejecutándose en tiempo exponencial (como el algoritmo de Bron-Kerbosch ) o especializados para familias de grafos como grafos planares o grafos perfectos para los cuales el problema puede resolverse en tiempo polinomial .

El término «clique», en su uso en la teoría de grafos, surgió del trabajo de Luce y Perry (1949) , quienes utilizaron subgrafos completos para modelar cliques (grupos de personas que se conocen entre sí) en redes sociales . Festinger (1949) empleó la misma definición en un artículo con términos menos técnicos. Ambos trabajos abordan la identificación de cliques en una red social mediante matrices. Para conocer otros esfuerzos por modelar cliques sociales desde una perspectiva de teoría de grafos, véanse, por ejemplo, Alba (1973) , Peay (1974) y Doreian y Woodard (1994) .

Muchos problemas diferentes de bioinformática se han modelado usando cliques. Por ejemplo, Ben-Dor, Shamir y Yakhini (1999) modelan el problema de agrupar datos de expresión genética como uno de encontrar el número mínimo de cambios necesarios para transformar un grafo que describe los datos en un grafo formado como la unión disjunta de cliques; Tanay, Sharan y Shamir (2002) discuten un problema de biclusterización similar para datos de expresión en el que se requiere que los clústeres sean cliques. Sugihara (1984) usa cliques para modelar nichos ecológicos en redes tróficas . Day y Sankoff (1986) describen el problema de inferir árboles evolutivos como uno de encontrar el máximo de cliques en un grafo que tiene como vértices características de la especie, donde dos vértices comparten una arista si existe una filogenia perfecta que combine esos dos caracteres. Samudrala y Moult (1998) modelan la predicción de la estructura de proteínas como un problema de búsqueda de cliques en un grafo cuyos vértices representan las posiciones de las subunidades de la proteína. Al buscar cliques en una red de interacción proteína-proteína , Spirin y Mirny (2003) encontraron grupos de proteínas que interactúan estrechamente entre sí y tienen pocas interacciones con proteínas fuera del grupo. El análisis de grafos de potencia es un método para simplificar redes biológicas complejas mediante la búsqueda de cliques y estructuras relacionadas en dichas redes.

En ingeniería eléctrica , Prihar (1956) utiliza cliques para analizar redes de comunicaciones, y Paull y Unger (1959) los utilizan para diseñar circuitos eficientes para calcular funciones booleanas parcialmente especificadas. Los cliques también se han utilizado en la generación automática de patrones de prueba : un clique grande en un grafo de incompatibilidad de posibles fallas proporciona un límite inferior en el tamaño de un conjunto de prueba. ^{[ 7 ]} Cong y Smith (1993) describen una aplicación de cliques para encontrar una partición jerárquica de un circuito electrónico en subunidades más pequeñas.

En química , Rhodes et al. (2003) utilizan grupos de compuestos para describir sustancias químicas en una base de datos química que tienen un alto grado de similitud con una estructura objetivo. Kuhl, Crippen y Friesen (1983) utilizan grupos de compuestos para modelar las posiciones en las que dos sustancias químicas se unirán entre sí.

• Juego de pandillas

• Weisstein, Eric W. , "Clique" , MathWorld
• Weisstein, Eric W. , "Número de camarilla" , MathWorld