stringtranslate.com

Clique (teoría de grafos)

Un gráfico con
  • 23 × camarillas de 1 vértice (los vértices),
  • 42 × camarillas de 2 vértices (los bordes),
  • 19 camarillas de 3 vértices (triángulos azul claro y azul oscuro) y
  • 2 camarillas de 4 vértices (áreas azul oscuro).
Los 11 triángulos celestes forman camarillas máximas. Las dos camarillas 4 de color azul oscuro son máximas y máximas, y el número de camarilla del gráfico es 4.

En teoría de grafos , una camarilla ( / ˈk l 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.

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 .

Definiciones

Una camarilla , C , en un grafo no dirigido G = ( V , E ) es un subconjunto de los vértices , CV , 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.

Matemáticas

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

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

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

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.

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 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 .

Aplicaciones

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í.

Véase también

Notas

  1. ^ El trabajo anterior de Kuratowski (1930) que caracterizaba los grafos planares mediante subgrafos completos prohibidos y bipartitos completos se formuló originalmente en términos topológicos en lugar de en términos de teoría de grafos.
  2. ^ Chang, Kloks y Lee (2001).
  3. ^ Turán (1941).
  4. ^ Graham, Rothschild y Spencer (1990).
  5. ^ Barthélemy, Leclerc y Monjardet (1986), página 200.
  6. ^ Carp (1972).
  7. ^ Hamzaoglu y Patel (1998).

Referencias

Enlaces externos