Clique (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 dos vértices distintos en la camarilla son adyacentes . Es decir, una camarilla de un grafo es un subgrafo inducido de que 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 encontrar si hay una camarilla de un tamaño dado en un grafo (el problema de la camarilla ) es NP-completo , pero a pesar de este resultado de dificultad, se han estudiado muchos algoritmos para encontrar camarillas.${\estilo de visualización G}$${\estilo de visualización G}$

Aunque el estudio de los subgrafos completos se remonta al menos a la reformulación grafo-teórica 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 la bioinformática .

Una camarilla , C , en un grafo no dirigido G = ( V , E ) es un subconjunto de los vértices , C ⊆ V , de modo que cada dos vértices distintos son adyacentes. Esto es equivalente a la condición de que el subgrafo inducido de G inducido 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 se puede extender mediante la inclusión de un vértice adyacente más, es decir, una camarilla que no existe exclusivamente dentro del conjunto de vértices de una camarilla más grande. Algunos autores definen las camarillas de una manera que requiere que sean maximalistas y usan otra terminología para subgrafos completos que no son maximalistas.

Una camarilla máxima de un grafo, G , es una camarilla tal que no existe ninguna camarilla con más vértices. Además, el número de camarillas ω ( 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 todos los bordes de G.

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

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

El opuesto de una camarilla es un conjunto independiente , en el sentido de que cada camarilla corresponde a un conjunto independiente en el grafo complementario . El problema de cobertura de camarillas se refiere a 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 la cantidad mínima de bicliques necesarios para cubrir todos los bordes del grafo.

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

• El teorema de Turán establece un límite 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, cada grafo con vértices y más de aristas debe contener una camarilla de tres vértices.${\estilo de visualización n}$${\displaystyle \scriptstyle \left\lfloor {\frac {n}{2}}\right\rfloor \cdot \left\lceil {\frac {n}{2}}\right\rceil }$
• El teorema de Ramsey establece que cada grafo o su grafo complementario 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 3 n vértices puede tener como máximo 3 ⁿ cliques maximales. Los grafos que cumplen esta cota son los grafos de Moon-Moser K _3,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 no demostrada, relaciona el tamaño del menor de la camarilla 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 establece que las familias de grafos definidas por la caracterización de grafos prohibidos tienen camarillas grandes o coclicas grandes .

Se pueden definir o caracterizar varias clases importantes de gráficos por sus camarillas:

• Un gráfico de conglomerados es un gráfico cuyos componentes conectados son camarillas.
• Un gráfico de bloques es un gráfico cuyos componentes biconectados son camarillas.
• Un grafo cordal es un grafo cuyos vértices pueden ordenarse en un orden de eliminación perfecto, un ordenamiento tal que los vecinos de cada vértice v que vienen después de v en el ordenamiento forman una camarilla.
• Un cografo es un grafo cuyos subgrafos inducidos tienen la propiedad de que cualquier camarilla maximal interseca cualquier conjunto maximal independiente en un solo vértice.
• Un grafo de intervalo es un grafo cuyas camarillas máximas se pueden ordenar de tal manera que, para cada vértice v , las camarillas que contienen a v son consecutivas en el orden.
• Un gráfico lineal es un gráfico cuyos bordes pueden ser cubiertos por camarillas disjuntas en sus bordes de tal manera que cada vértice pertenece exactamente a dos de las camarillas en la cubierta.
• Un gráfico perfecto es un gráfico en el que el número de camarilla es igual al número cromático en cada subgráfico inducido .
• Un gráfico dividido es un gráfico en el que algún grupo contiene al menos un punto final de cada arista.
• Un gráfico libre de triángulos es un gráfico que no tiene camarillas aparte de sus vértices y aristas.

Además, muchas otras construcciones matemáticas implican camarillas en gráficos. Entre ellas,

• El complejo de camarilla de un grafo G es un complejo simplicial abstracto X ( G ) con un símplex para cada camarilla en G
• Un grafo simplex es un grafo no dirigido κ( G ) con un vértice para 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]
• La suma de camarillas es un método para combinar dos gráficos fusionándolos a lo largo de una camarilla compartida.
• El ancho de camarilla es una noción de la complejidad de un grafo en términos del número mínimo de etiquetas de vértices 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 un ancho de camarilla de uno son exactamente las uniones disjuntas de camarillas.
• El número de intersección de un gráfico es el número mínimo de camarillas necesarias para cubrir todos los bordes del gráfico.
• El gráfico de camarillas de un grafo es el gráfico 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 a los grafos planares mediante subdivisiones y menores completos prohibidos y bipartitos completos , respectivamente.

En informática , 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 se puede resolver en tiempo polinomial .

La palabra "clique", en su uso en 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 . La misma definición fue utilizada por Festinger (1949) en un artículo que utilizó términos menos técnicos. Ambos trabajos tratan sobre el descubrimiento de cliques en una red social utilizando matrices. Para los esfuerzos continuos para modelar cliques sociales en teoría de grafos, véase, por ejemplo, Alba (1973), Peay (1974) y Doreian y Woodard (1994).

Muchos problemas diferentes de la bioinformática se han modelado utilizando camarillas. 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 gráfico que describe los datos en un gráfico formado como la unión disjunta de camarillas; Tanay, Sharan y Shamir (2002) discuten un problema de biclustering similar para datos de expresión en el que se requiere que los grupos sean camarillas. Sugihara (1984) utiliza camarillas para modelar nichos ecológicos en redes alimentarias . Day y Sankoff (1986) describen el problema de inferir árboles evolutivos como uno de encontrar camarillas máximas en un gráfico que tiene como vértices características de la especie, donde dos vértices comparten un borde si existe una filogenia perfecta que combina esos dos caracteres. Samudrala y Moult (1998) modelan la predicción de la estructura de las proteínas como un problema de búsqueda de camarillas en un grafo cuyos vértices representan posiciones de subunidades de la proteína. Y al buscar camarillas 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 al encontrar camarillas y estructuras relacionadas en estas redes.

En ingeniería eléctrica , Prihar (1956) utiliza camarillas para analizar redes de comunicaciones, y Paull y Unger (1959) las utilizan para diseñar circuitos eficientes para calcular funciones booleanas parcialmente especificadas. Las camarillas también se han utilizado en la generación automática de patrones de prueba : una camarilla grande en un gráfico 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 camarillas 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 cliques 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 cliques para modelar las posiciones en las que dos sustancias químicas se unirán entre sí.

• Juego de camarilla

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