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 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.
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 , 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.
Matemáticas
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.
Según un resultado de Moon y Moser (1965), un grafo con 3 n vértices puede tener como máximo 3 n 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.
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 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.
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í.
^ 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.
^ Chang, Kloks y Lee (2001).
^ Turán (1941).
^ Graham, Rothschild y Spencer (1990).
^ Barthélemy, Leclerc y Monjardet (1986), página 200.
^ Carp (1972).
^ Hamzaoglu y Patel (1998).
Referencias
Alba, Richard D. (1973), "Una definición de teoría de grafos de una camarilla sociométrica" (PDF) , Journal of Mathematical Sociology , 3 (1): 113–126, doi :10.1080/0022250X.1973.9989826, archivado (PDF) desde el original el 2011-05-03 , consultado el 2009-12-14.
Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), "Sobre el uso de conjuntos ordenados en problemas de comparación y consenso de clasificaciones", Journal of Classification , 3 (2): 187–224, doi :10.1007/BF01894188, S2CID 6092438.
Ben-Dor, Amir; Shamir, Ron; Yakhini, Zohar (1999), "Agrupamiento de patrones de expresión genética", Journal of Computational Biology , 6 (3–4): 281–297, CiteSeerX 10.1.1.34.5341 , doi :10.1089/106652799318274, PMID 10582567.
Chang, Maw-Shang; Kloks, Ton; Lee, Chuan-Min (2001), "Transversales de clique máximas", Graph-theoretic concepts in computer science (Boltenhagen, 2001) , Lecture Notes in Comput. Sci., vol. 2204, Springer, Berlín, págs. 32–43, doi :10.1007/3-540-45477-2_5, ISBN 978-3-540-42707-0, Sr. 1905299.
Cong, J.; Smith, M. (1993), "Un algoritmo de agrupamiento ascendente paralelo con aplicaciones a la partición de circuitos en el diseño VLSI", Proc. 30th International Design Automation Conference , págs. 755–760, CiteSeerX 10.1.1.32.735 , doi :10.1145/157485.165119, ISBN 978-0897915779, S2CID 525253.
Day, William HE; Sankoff, David (1986), "Complejidad computacional de la inferencia de filogenias por compatibilidad", Systematic Zoology , 35 (2): 224–229, doi :10.2307/2413432, JSTOR 2413432.
Doreian, Patrick; Woodard, Katherine L. (1994), "Definición y localización de núcleos y límites de redes sociales", Redes sociales , 16 (4): 267–293, doi :10.1016/0378-8733(94)90013-2.
Erdős, Paul ; Szekeres, George (1935), "Un problema combinatorio en geometría" (PDF) , Compositio Mathematica , 2 : 463–470, archivado (PDF) desde el original el 2020-05-22 , consultado el 2009-12-19.
Festinger, Leon (1949), "El análisis de sociogramas utilizando álgebra matricial", Human Relations , 2 (2): 153–158, doi :10.1177/001872674900200205, S2CID 143609308.
Hamzaoglu, I.; Patel, JH (1998), "Algoritmos de compactación de conjuntos de prueba para circuitos combinacionales", Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design , págs. 283–289, doi : 10.1145/288548.288615 , ISBN 978-1581130089, S2CID12258606 .
Karp, Richard M. (1972), "Reducibility among combinatorial problems", en Miller, RE; Thatcher, JW (eds.), Complexity of Computer Computations (PDF) , Nueva York: Plenum, pp. 85–103, archivado desde el original (PDF) el 29 de junio de 2011 , consultado el 13 de diciembre de 2009.
Kuhl, FS; Crippen, GM; Friesen, DK (1983), "Un algoritmo combinatorio para calcular la unión de ligandos", Journal of Computational Chemistry , 5 (1): 24–34, doi :10.1002/jcc.540050105, S2CID 122923018.
Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en Topologie" (PDF) , Fundamenta Mathematicae (en francés), 15 : 271–283, doi : 10.4064/fm-15-1-271-283 , archivado ( PDF) del original el 23 de julio de 2018 , recuperado 2009-12-19.
Luce, R. Duncan ; Perry, Albert D. (1949), "Un método de análisis matricial de la estructura de grupo", Psychometrika , 14 (2): 95–116, doi :10.1007/BF02289146, hdl : 10.1007/BF02289146 , PMID 18152948, S2CID 16186758.
Paull, MC; Unger, SH (1959), "Minimización del número de estados en funciones de conmutación secuencial especificadas de forma incompleta", IRE Transactions on Electronic Computers , EC-8 (3): 356–367, doi :10.1109/TEC.1959.5222697.
Peay, Edmund R. (1974), "Estructuras jerárquicas de camarillas", Sociometry , 37 (1): 54–65, doi :10.2307/2786466, JSTOR 2786466.
Prihar, Z. (1956), "Propiedades topológicas de las redes de telecomunicaciones", Actas del IRE , 44 (7): 927–933, doi :10.1109/JRPROC.1956.275149, S2CID 51654879.
Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: búsqueda de similitudes en bases de datos 3D mediante detección de camarillas", Journal of Chemical Information and Computer Sciences , 43 (2): 443–448, doi :10.1021/ci025605o, PMID 12653507.
Samudrala, Ram; Moult, John (1998), "Un algoritmo de teoría de grafos para el modelado comparativo de la estructura de proteínas", Journal of Molecular Biology , 279 (1): 287–302, CiteSeerX 10.1.1.64.8918 , doi :10.1006/jmbi.1998.1689, PMID 9636717.
Spirin, Victor; Mirny, Leonid A. (2003), "Complejos proteicos y módulos funcionales en redes moleculares", Actas de la Academia Nacional de Ciencias , 100 (21): 12123–12128, doi : 10.1073/pnas.2032324100 , PMC 218723 , PMID 14517352.
Sugihara, George (1984), "Teoría de grafos, homología y redes alimentarias", en Levin, Simon A. (ed.), Population Biology , Proc. Symp. Appl. Math., vol. 30, págs. 83–101.
Tanay, Amos; Sharan, Roded; Shamir, Ron (2002), "Descubrimiento de biclusters estadísticamente significativos en datos de expresión génica", Bioinformatics , 18 (Suppl. 1): S136–S144, doi : 10.1093/bioinformatics/18.suppl_1.S136 , PMID 12169541.
Turán, Paul (1941), "Sobre un problema extremo en teoría de grafos", Matematikai és Fizikai Lapok (en húngaro), 48 : 436–452
