Clique

En el área matemática de la teoría de grafos, una camarilla o clique es un subconjunto de vértices de un gráfico 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 deeso 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 en grafos. Las camarillas también se han estudiado en informática: la tarea de encontrar si hay una camarilla de un tamaño determinado en un gráfico (el problema de la camarilla) es NP-completa, pero a pesar de este resultado de dureza, se han estudiado muchos algoritmos para encontrar camarillas.

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

Definiciones

Una camarilla, C, en un gráfico no dirigido G = (V, E) es un subconjunto de los vértices, C ⊆ V, tal 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 máxima es una camarilla que no se puede extender incluyendo 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 máximas y usan otra terminología para subgrafos completos que no son máximos.

Una camarilla máxima de un grafo, G, es una camarilla, tal que no hay camarilla 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 todos los bordes de G.

El número de cobertura de clique de un grafo G es el menor número de cliques de G cuya unión cubre el conjunto de vértices V del grafo.

Una clique máxima transversal 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.

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

Un concepto relacionado es un biclique, un subgrafo bipartito completo. La dimensión bipartita de un gráfico es el número mínimo de biliques necesarios para cubrir todos los bordes del gráfico.

Matemáticas

Los resultados matemáticos relacionados con las camarillas incluyen lo siguiente.

• El teorema de Turán da un límite inferior al tamaño de una camarilla en gráficos densos. Si un gráfico tiene suficientes aristas, debe contener una camarilla grande. Por ejemplo, cada gráfico con vértices y más de bordes debe contener una camarilla de tres vértices.
• El teorema de Ramsey establece que cada gráfico o su gráfico complementario contiene una camarilla con al menos un número logarítmico de vértices.
• Según un resultado de Moon & Moser (1965), un grafo con 3 n vértices puede tener como máximo 3 clicas máximas. Los gráficos que cumplen este límite son los gráficos de Luna-Moser K _3,3,..., un caso especial de los gráficos 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 de la camarilla menor más grande en un gráfico (su número de Hadwiger) con su número cromático.
• La conjetura de Erdős-Faber-Lovász es otra afirmación no probada que relaciona la coloración de gráficos con las camarillas.

Varias clases importantes de gráficos pueden definirse o caracterizarse por sus clicas:

• 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 se pueden ordenar en una ordenación de eliminación perfecta, una ordenación tal que los vecinos de cada vértice v que vienen después de v en la ordenación forman una camarilla.
• Un cografo es un grafo cuyos subgrafos inducidos tienen la propiedad de que cualquier camarilla máxima se cruza con cualquier conjunto independiente máximo en un solo vértice.
• Un grafo de intervalo es un grafo cuyas cliques máximas se pueden ordenar de tal manera que, para cada vértice v, las cliques que contienen v son consecutivas en el ordenamiento.
• Un gráfico de líneas es un gráfico cuyos bordes pueden cubrirse con camarillas de borde disjunto 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 clique es igual al número cromático en cada subgrafo inducido.
• Un gráfico dividido es un gráfico en el que alguna camarilla contiene al menos un punto final de cada borde.
• Un grafo sin triángulos es un grafo que no tiene clics aparte de sus vértices y aristas.

Además, muchas otras construcciones matemáticas involucran camarillas en gráficos. Entre ellos,

• El complejo clique de un grafo G es un complejo simplicial abstracto X (G) con un símplex para cada clique en G
• Un grafo simplex es un grafo no dirigido κ(G) con un vértice para cada camarilla en un gráfico G y una arista que conecta dos camarillas que difieren en un solo vértice. Es un ejemplo de gráfico mediano y está asociado con un álgebra mediana sobre las camarillas de un gráfico: la mediana m (A, B, C) de tres camarillas A, B y C es la camarilla cuyos vértices pertenecen al menos a dos de las camarillas A, B y C.
• La suma de camarilla es un método para combinar dos gráficos fusionándolos a lo largo de una camarilla compartida.
• Clique-width es una noción de la complejidad de un gráfico en términos del número mínimo de etiquetas de vértice distintas necesarias para construir el gráfico a partir de uniones disjuntas, operaciones de reetiquetado y operaciones que conectan todos los pares de vértices con etiquetas dadas. Los gráficos con ancho de camarilla 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 clique de un gráfico es el gráfico de intersección de sus cliques máximos.

Los conceptos estrechamente relacionados con los subgrafos completos son las subdivisiones de los gráficos completos y los menores de gráficos completos. En particular, el teorema de Kuratowski y el teorema de Wagner caracterizan grafos planos por subdivisiones bipartitas completas y completas prohibidas y menores, respectivamente.

Ciencias de la Computación

En informática, el problema de la camarilla es el problema computacional de encontrar una camarilla máxima, o todas las camarillas, en un gráfico dado. Es NP-completo, uno de los 21 problemas NP-completos de Karp. También es intratable de 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 graficar familias, como gráficos planos o gráficos perfectos para los que el problema se puede resolver en tiempo polinomial.

Aplicaciones

La palabra "camarilla", en su uso teórico de grafos, surgió del trabajo de Luce & Perry (1949), quienes utilizaron subgrafos completos para modelar camarillas (grupos de personas que se conocen entre sí) en las redes sociales. La misma definición fue usada por Festinger (1949) en un artículo usando términos menos técnicos. Ambos trabajos tratan sobre el descubrimiento de camarillas en una red social utilizando matrices. Para los esfuerzos continuados por modelar las camarillas sociales de forma gráfica, véase, por ejemplo, Alba (1973), Peay (1974) y Doreian y Woodard (1994).

Se han modelado muchos problemas diferentes de la bioinformática utilizando camarillas. Por ejemplo, Ben-Dor, Shamir y Yakhini (1999) modelan el problema de agrupar datos de expresión génica 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) analizan un problema de biagrupación similar para datos de expresión en los que se requiere que las agrupaciones sean camarillas. Sugihara (1984) usa 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 & Moult (1998) modela la predicción de la estructura de la proteína como un problema de encontrar camarillas en un gráfico 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 gráficos de potencia es un método para simplificar redes biológicas complejas al encontrar camarillas y estructuras relacionadas en estas redes. Mirny (2003) encontró grupos de proteínas que interactúan estrechamente entre sí y tienen pocas interacciones con proteínas fuera del grupo. El análisis de gráficos de potencia es un método para simplificar redes biológicas complejas al encontrar camarillas y estructuras relacionadas en estas redes. Mirny (2003) encontró grupos de proteínas que interactúan estrechamente entre sí y tienen pocas interacciones con proteínas fuera del grupo. El análisis de gráficos 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) usa camarillas para analizar redes de comunicaciones, y Paull y Unger (1959) las usan 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. Cong y Smith (1993) describen una aplicación de clicas 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 camarillas para describir productos químicos en una base de datos de productos químicos que tienen un alto grado de similitud con una estructura de destino. Kuhl, Crippen y Friesen (1983) utilizan camarillas para modelar las posiciones en las que dos sustancias químicas se unirán entre sí.