Camarillas en gráfico

Una camarilla es una colección de vértices en un gráfico no dirigido G tal que cada dos vértices diferentes en la camarilla están cerca, lo que implica que el subgrafo inducido está completo. Las camarillas son un tema fundamental en la teoría de grafos y se emplean en muchos otros problemas matemáticos y creaciones de gráficos. A pesar de que el objetivo de determinar si existe una camarilla de cierto tamaño en una red (el problema de la camarilla) es NP-completo, se han investigado varios métodos para detectar camarillas. Una camarilla máxima es aquella que no se puede agrandar agregando un vértice vecino más, es decir, una que no reside solo dentro del conjunto de vértices de una camarilla más grande.

Una camarilla en un grafo no dirigido es un subgrafo completo del grafo dado. Un subgrafo completo es aquel en el que todos sus vértices están vinculados a todos sus otros vértices. El problema de Max-Clique es el desafío computacional de ubicar la camarilla máxima del gráfico. Muchos problemas del mundo real hacen uso de la camarilla de Max. Considere un programa de red social en el que los vértices de un gráfico reflejan los perfiles de las personas y los bordes representan el conocimiento mutuo. Una camarilla en este gráfico indica un grupo de personas que se conocen entre sí.

Análisis: 

El análisis de problemas de Max-Clique es un algoritmo no determinista. En este enfoque, primero tratamos de encontrar una colección de k vértices diferentes y luego vemos si estos vértices forman un gráfico completo. Este problema no se puede resolver utilizando un método determinista de tiempo polinomial. Este es un problema NP-Complete .

Para descubrir una camarilla máxima, uno puede escanear todos los subconjuntos metódicamente, pero este tipo de búsqueda de fuerza bruta requiere mucho tiempo para redes con más de unos pocos cientos de vértices.

Una camarilla máxima de un gráfico, G, es una camarilla en la que ninguna camarilla tiene más vértices. Además, el número de camarilla ω(G) de un gráfico G es el número de vértices en la camarilla más grande del gráfico. Las camarillas aparecen en una variedad de campos de la teoría de grafos y la combinatoria, incluida la coloración de gráficos y la teoría de codificación de corrección de errores. Una camarilla k es una camarilla de tamaño k. (aunque este término también se usa a veces para referirse a un conjunto máximo de vértices que están a una distancia no mayor que k entre sí). 0-camarillas representan el conjunto vacío (conjuntos de 0 vértices), 1-camarillas representan vértices, 2-camarillas representan bordes y 3-camarillas representan 3 ciclos.

El polinomio clique de un gráfico G se define como

donde c _k es el número de camarillas de tamaño k, con c ₀ =1, c ₁ =|G| igual al número de vértices de G, c ₂ =m(G) igual al número de aristas de G, etc.

Teoremas sobre la camarilla

• El teorema de Turan restringe el tamaño de una camarilla en redes densas. Debe existir una gran camarilla si un gráfico tiene un número suficiente de aristas. Por ejemplo, toda red con n vértices y más de \frac {n}{2}. Las aristas \frac{n}{2} deben tener una camarilla de tres vértices.
• De acuerdo con el teorema de Ramsey, cualquier gráfico o su gráfico complementario tiene una camarilla con al menos un número logarítmico de vértices.
• Moon y Moser (1965) descubrieron que una red con 3n vértices solo puede contener 3n cliques como máximo. Los gráficos de Moon-Moser son los que cumplen esta restricción.

Las camarillas se pueden usar para identificar clases de gráficos:

• Un gráfico de conglomerados es un gráfico con camarillas como sus componentes vinculados.
• Un gráfico de bloques es un gráfico con camarillas como componentes biconectados.
• Un grafo cordal es aquel en el que los vértices se pueden organizar en un orden de eliminación perfecta, en el que los vecinos de cada vértice v que aparecen después de v en el orden forman una camarilla.
• Un cografo es un grafo en el que todos sus subgrafos inducidos se cruzan con cualquier camarilla máxima en un solo vértice.
• Un grafo de intervalo es aquel en el que las camarillas máximas pueden disponerse de tal manera que las camarillas que contienen v son sucesivas en el ordenamiento de cada vértice v.
• Un gráfico de líneas es uno con bordes que pueden estar cubiertos por clicas disjuntas de borde, de modo que cada vértice pertenece exactamente a dos de las clicas en la cubierta.
• Un gráfico perfecto es aquel en el que el número de clique en cada subgrafo inducido es igual al número cromático.
• Un gráfico dividido es aquel en el que al menos un punto final de cada borde está contenido dentro de una camarilla.
• Un grafo sin triángulos es uno sin clics además de sus vértices y aristas.

¿Qué es el problema de la camarilla?

El problema de las camarillas es un desafío informático que consiste en ubicar las camarillas en un gráfico. Tiene múltiples formulaciones basadas en qué camarillas deben ubicarse y qué información sobre las camarillas debe obtenerse.
Encontrar una camarilla máxima, encontrar una camarilla de peso máximo en un gráfico ponderado, enumerar todas las camarillas máximas y resolver el problema de decisión de verificar si un gráfico tiene una camarilla mayor que un tamaño particular son formulaciones comunes del problema de camarilla.

La mayoría de las variantes de problemas de camarilla son difíciles. El problema de la elección de la camarilla (uno de los 21 problemas NP-completos de Karp) es NP-completo. Encontrar la camarilla más grande es tanto intratable como de parámetro fijo y difícil de estimar. Además, enumerar todas las camarillas máximas puede llevar un tiempo exponencial, ya que hay gráficos con muchas camarillas máximas exponencialmente.

Identificación de una única camarilla máxima

Un método codicioso básico puede encontrar una sola camarilla más grande. Hacer crecer la camarilla actual un vértice a la vez recorriendo los vértices restantes del gráfico, comenzando con una camarilla arbitraria (por ejemplo, cualquier vértice individual o incluso el conjunto completo). Para cada vértice v examinado por este ciclo, agregue v a la camarilla si está cerca de cada vértice actualmente en la camarilla, de lo contrario, descarte v. Este algoritmo es lineal en el tiempo. Debido a la simplicidad con la que se pueden encontrar las camarillas máximas, así como a su posible tamaño modesto, se ha prestado más atención al desafío algorítmico mucho más difícil de encontrar una camarilla máxima o grande que a la dificultad de encontrar una camarilla máxima única. .

camarillas de tamaño fijo

Usando una técnica de fuerza bruta, uno puede probar si un gráfico G tiene una camarilla de k-vértice y localizar cualquier camarilla que la tenga. Este método inspecciona cada subgrafo con k vértices para ver si constituye una camarilla. Toma tiempo O(nkk2), como se representa en notación O grande. Esto se debe al hecho de que hay subgrafos O(nk) para examinar, cada uno con aristas O(k2) cuya presencia en G debe verificarse. Como resultado, cuando k es una constante fija, el problema se puede resolver en tiempo polinomial. Cuando k no tiene un valor establecido y, en cambio, puede fluctuar como parte de la entrada del problema, el tiempo es exponencial.

¿Cuáles son las aplicaciones de Clique?

Considere una red social en la que los vértices representan personas y los bordes indican conocimiento mutuo. Luego, una camarilla representa un subconjunto de personas que se conocen entre sí, y se pueden usar algoritmos de búsqueda de camarillas para localizar estos grupos de amigos comunes.

En bioinformática, el problema de la camarilla tiene varias aplicaciones. Por ejemplo, Ben-Dorr, Shamir y Yakima (1999) caracterizan el problema de agrupar datos de expresión génica como una búsqueda del menor número de modificaciones requeridas para convertir un gráfico que describe los datos en un gráfico formado por la unión disjunta de camarillas.

Pregunta de muestra

Pregunta 1: ¿Cómo se ubica una camarilla en un gráfico?
Responder: 

Para ubicar una camarilla G:
Digamos que G tiene n vértices.
Encuentre el vértice de grado mínimo factible v en G.
Si v tiene un grado de n 1, deténgase; G es una camarilla, y la camarilla más grande en G tiene un tamaño de n.
De lo contrario, elimine v y todos sus bordes de G. En el gráfico más pequeño, encuentre la camarilla más grande.

Pregunta 2: ¿Cuál es el número de camarillas en un gráfico?
Responder: 

Un gráfico completo se conoce comúnmente como una camarilla. El número de camarilla de G es el tamaño de la camarilla más grande que se puede formar a partir de las aristas y vértices de G. En consecuencia, la penúltima afirmación que precede a estas definiciones puede escribirse de la siguiente manera: el número de color de un gráfico es al menos su número de camarilla.

Pregunta 3: ¿Es posible que un grafo tenga varias clicas?
Responder: 

Si el complemento es bipartito, el grafo se puede dividir en dos conjuntos U y V, sin aristas que unen los vértices del mismo conjunto. Esto indica que estos conjuntos U y V están totalmente relacionados en el gráfico original. Como resultado, el gráfico original puede dividirse en dos Cliques.