Camarillas de 19 × 3 vértices (triángulos azul claro y oscuro), y
Camarillas de 2 × 4 vértices (áreas de color azul oscuro).
Los 11 triángulos de color azul claro forman camarillas máximas. Las dos 4 camarillas de color azul oscuro son máximas y máximas, y el número de camarilla del gráfico es 4.
En el área matemática de la teoría de grafos , una camarilla ( / ˈk l iː k / o / ˈk l ɪ k / ) 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 de un grafo 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 gráficos. 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 subgrafos completos se remonta al menos a la reformulación grafica de la teoría de Ramsey por Erdős & Szekeres (1935), [1] el término camarilla proviene de Luce & Perry (1949), quienes utilizaron subgrafos completos en redes sociales para camarillas modelo 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 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 gráfico 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 ampliar 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 gráfico, G , es una camarilla, tal que no hay camarilla con 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 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 camarillas de un gráfico G es el número más pequeño de camarillas de G cuya unión cubre el conjunto de vértices V del gráfico.
Una camarilla transversal 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]
Lo opuesto a una camarilla es un conjunto independiente , en el sentido de que cada camarilla corresponde a un conjunto independiente en el gráfico de 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 biclique , un subgrafo bipartito completo . La dimensión bipartita de un gráfico es el número mínimo de bicliques necesarias para cubrir todos los bordes del gráfico.
Matemáticas
Los resultados matemáticos relacionados con las camarillas incluyen los siguientes.
El teorema de Turán da un límite inferior al tamaño de una camarilla en gráficos densos . [3] Si un gráfico tiene suficientes aristas, debe contener una camarilla grande. Por ejemplo, todo gráfico con vértices y más de aristas debe contener una camarilla de tres vértices.
El teorema de Ramsey establece que todo gráfico o su complemento 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 gráfico con 3 n vértices puede tener como máximo 3 n camarillas máximas. Los gráficos que cumplen con este límite son los gráficos de Moon-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.
Un gráfico cordal es un gráfico cuyos vértices se pueden ordenar en un orden de eliminación perfecta, un orden 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 gráfico cuyos subgrafos inducidos tienen la propiedad de que cualquier camarilla máxima interseca cualquier conjunto máximo independiente en un solo vértice.
Un gráfico de intervalo es un gráfico cuyas camarillas máximas se pueden ordenar de tal manera que, para cada vértice v , las camarillas que contienen v son consecutivas en el orden.
Un gráfico lineal es un gráfico cuyos bordes pueden estar cubiertos por camarillas con bordes disjuntos de tal manera que cada vértice pertenezca exactamente a dos de las camarillas de la cubierta.
Un gráfico simplex es un gráfico no dirigido κ( G ) con un vértice para cada camarilla en un gráfico G y un borde que conecta dos camarillas que difieren por un solo vértice. Es un ejemplo de gráfico de mediana y está asociado con un álgebra de mediana sobre las camarillas de una gráfica: 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. [5]
La suma de camarilla 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 gráfico en términos del número mínimo de etiquetas de vértices 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.
La palabra "camarilla", en su uso en teoría de grafos, surgió del trabajo de Luce y Perry (1949), quienes utilizaron subgrafos completos para modelar camarillas (grupos de personas que se conocen entre sí) en las redes sociales . Festinger (1949) utilizó la misma definición en un artículo utilizando términos menos técnicos. Ambos trabajos tratan de descubrir camarillas en una red social utilizando matrices. Para los esfuerzos continuos por modelar gráficamente las camarillas sociales, véanse, 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 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) analizan un problema de biclustering similar para datos de expresión en el que se requiere que los clusters sean camarillas. Sugihara (1984) utiliza camarillas para modelar nichos ecológicos en las redes alimentarias . Day y Sankoff (1986) describen el problema de inferir árboles evolutivos como el de encontrar camarillas máximas en un gráfico que tiene como vértices características de la especie, donde dos vértices comparten una arista 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 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 mediante la búsqueda de 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 camarillas 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 camarillas para modelar las posiciones en las que dos sustancias químicas se unirán entre sí.
↑ El trabajo anterior de Kuratowski (1930), que caracteriza los grafos planos mediante subgrafos bipartitos completos y completos prohibidos , se redactó originalmente en términos topológicos más que teóricos de grafos.
^ Chang, Kloks y Lee (2001).
↑ Turán (1941).
^ Graham, Rothschild y Spencer (1990).
^ Barthélemy, Leclerc y Monjardet (1986), página 200.
^ Karp (1972).
^ Hamzaoglu y Patel (1998).
Referencias
Alba, Richard D. (1973), "Una definición teórica de grafos de una camarilla sociométrica" (PDF) , Journal of Mathematical Sociology , 3 (1): 113–126, doi :10.1080/0022250X.1973.9989826, archivado (PDF) del original el 3 de mayo de 2011 , consultado el 14 de diciembre de 2009.
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), "Agrupación 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, tonelada; Lee, Chuan-Min (2001), "Maximum clique transversals", Conceptos de teoría de grafos en informática (Boltenhagen, 2001) , Lecture Notes in Comput. Ciencia, vol. 2204, Springer, Berlín, págs. 32–43, doi :10.1007/3-540-45477-2_5, ISBN 978-3-540-42707-0, señor 1905299.
Cong, J.; Smith, M. (1993), "Un algoritmo de agrupamiento ascendente paralelo con aplicaciones para la partición de circuitos en el diseño VLSI", Proc. 30.a Conferencia Internacional de Automatización del Diseño , págs. 755–760, CiteSeerX 10.1.1.32.735 , doi :10.1145/157485.165119, ISBN 978-0897915779, S2CID 525253.
Día, William HE; Sankoff, David (1986), "Complejidad computacional de inferir filogenias por compatibilidad", Zoología sistemática , 35 (2): 224–229, doi :10.2307/2413432, JSTOR 2413432.
Doreian, Patricio; Woodard, Katherine L. (1994), "Definición y localización de núcleos y límites de las 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 22 de mayo de 2020 , consultado el 19 de diciembre de 2009.
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 Conferencia internacional IEEE/ACM sobre diseño asistido por ordenador , págs. 283–289, doi : 10.1145/288548.288615 , ISBN 978-1581130089, S2CID 12258606.
Karp, Richard M. (1972), "Reducibilidad entre problemas combinatorios", en Miller, RE; Thatcher, JW (eds.), Complexity of Computer Computations (PDF) , Nueva York: Plenum, págs. 85-103, archivado desde el original (PDF) el 29 de junio de 2011 , consultado el 13 de diciembre de 2009..
Kuhl, FS; Crippen, gerente general; 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 , consultado el 19 de diciembre de 2009.
Luce, R. Duncan ; Perry, Albert D. (1949), "Un método de análisis matricial de 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), "Minimizar el 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 de camarilla jerárquicas", Sociometría , 37 (1): 54–65, doi :10.2307/2786466, JSTOR 2786466.
Prihar, Z. (1956), "Propiedades topológicas de las redes de telecomunicaciones", Actas de la IRE , 44 (7): 927–933, doi :10.1109/JRPROC.1956.275149, S2CID 51654879.
Rodas, Nicolás; 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 teórico 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, Víctor; Mirny, Leonid A. (2003), "Complejos de proteínas 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.), Biología de poblaciones , Proc. Síntoma. Aplica. Matemáticas, vol. 30, págs. 83-101.
Tanay, Amós; Sharan, rodado; Shamir, Ron (2002), "Descubrimiento de biclusters estadísticamente significativos en datos de expresión genética", Bioinformatics , 18 (Supl. 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
