En la matemática área de la teoría de grafos , un clique ( / k l i k / o / k l ɪ k / ) es un subconjunto de vértices de un grafo no dirigido de tal manera que cada dos vértices distintos en la camarilla son adyacentes; es decir, su subgrafo inducido está completo . Las camarillas son uno de los conceptos básicos de la teoría de gráficos y se utilizan en muchos otros problemas matemáticos y construcciones en gráficos. También se han estudiado camarillas 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 subgrafías completas se remonta al menos a la reformulación teórica de grafos de la teoría de Ramsey por Erdős & Szekeres (1935) , [1] el término camarilla proviene de Luce & Perry (1949) , quien utilizó subgrafías completas en redes sociales para modelos de 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 bioinformática .
Definiciones [ editar ]
Una camarilla , C , en un gráfico 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 es 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 extender al incluir 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 completar subgrafías que no son máximas.
Una camarilla máxima de un gráfico, G , es una camarilla, de modo que no hay una camarilla con más vértices. Por otra parte, el número clique ω ( 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 juntos cubren todos los bordes de G .
El número de cubierta de camarilla 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 de la gráfica.
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 del complemento . El problema de la cobertura de la camarilla se refiere a 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 bicliques necesarios para cubrir todos los bordes del gráfico.
Matemáticas [ editar ]
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 una gráfica tiene suficientes bordes, debe contener una camarilla grande. Por ejemplo, cada gráfico con vértices y más de los bordes deben contener una camarilla de tres vértices.
- El teorema de Ramsey establece que cada gráfica o su gráfica complementaria contiene una camarilla con al menos un número logarítmico de vértices. [4]
- Según un resultado de Moon & Moser (1965) , un gráfico con 3 n vértices puede tener como máximo 3 n camarillas máximas. Las gráficas que cumplen este límite son las gráficas de Luna-Moser K 3,3, ... , un caso especial de las gráficas de Turán que surgen como los casos extremos en el teorema de Turán.
- La conjetura de Hadwiger , aún no probada, 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 comprobada que relaciona el color de los gráficos con las camarillas.
Varias clases importantes de gráficos pueden definirse o caracterizarse por sus camarillas:
- Un gráfico de clúster es un gráfico cuyos componentes conectados son camarillas.
- Un gráfico de bloque es un gráfico cuyos componentes biconéctados son camarillas.
- Un gráfico cordal es un gráfico cuyos vértices se pueden ordenar en un orden de eliminación perfecto, un orden tal que los vecinos de cada vértice v que vienen después de v en el orden forman una camarilla.
- Una cografía es una gráfica cuyas subgrafías inducidas tienen la propiedad de que cualquier camarilla máxima se cruza con cualquier conjunto independiente máximo 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 disjuntas de bordes 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 camarilla es igual al número cromático en cada subgrafía inducida .
- Un gráfico dividido es un gráfico en el que una camarilla contiene al menos un punto final de cada borde.
- Un gráfico sin triángulo es un gráfico que no tiene camarillas aparte de sus vértices y bordes.
Además, muchas otras construcciones matemáticas involucran camarillas en los gráficos. Entre ellos,
- El complejo de camarilla de un gráfico G es un complejo simplicial abstracto X ( G ) con un simplex para cada camarilla en G
- 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 en un solo vértice. Es un ejemplo de gráfica mediana , y está asociada con un álgebra mediana en 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 camarillas es un método para combinar dos gráficos fusionándolos a lo largo de una camarilla compartida.
- El ancho de la camarilla 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 camarilla de un gráfico es el gráfico de intersección de sus camarillas máximas.
Los conceptos estrechamente relacionados con los subgrafos completos son subdivisiones de gráficos completos y gráficos menores completos . En particular, el teorema de Kuratowski y del teorema de Wagner caracterizan planar gráficos por prohibidos completos y completos bipartitos subdivisiones y menores, respectivamente.
Informática [ editar ]
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-complete , uno de los 21 problemas de Karp NP-complete . [6] También es intratable de parámetros fijos y difícil de aproximar . Sin embargo, se han desarrollado muchos algoritmos para calcular camarillas, que se ejecutan en tiempo exponencial (como el algoritmo Bron-Kerbosch ) o se especializan para graficar familias como gráficos planos o gráficos perfectos para los que se puede resolver el problema.tiempo polinómico .
Aplicaciones [ editar ]
La palabra "camarilla", en su uso teórico de grafos, surgió del trabajo de Luce & Perry (1949) , quien utilizó subgrafías completas 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 que utilizaba términos menos técnicos. Ambos trabajos tratan de descubrir camarillas en una red social utilizando matrices. Para los esfuerzos continuos para modelar gráficamente las camarillas sociales, véase, por ejemplo, Alba (1973) , Peay (1974) y Doreian & 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 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) discuten un problema similar de biclustering para los datos de expresión en el que los grupos deben ser 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 las características de la especie, donde dos vértices comparten un borde si existe una filogenia perfecta que combine esos dos caracteres. Samudrala y Moult (1998) modelan la predicción de la estructura de la proteína como un problema para 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. Análisis gráfico 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) usa camarillas para analizar redes de comunicaciones, y Paull y Unger (1959) las usan para diseñar circuitos eficientes para computar funciones booleanas parcialmente especificadas. Las camarillas también se han utilizado en la generación automática de patrones de prueba : una gran camarilla 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) usan camarillas para describir productos químicos en una base de datos químicos que tienen un alto grado de similitud con una estructura objetivo. Kuhl, Crippen y Friesen (1983) usan camarillas para modelar las posiciones en las que dos productos químicos se unirán entre sí.
(Redirigido desde el número de Clique )
En la matemática área de la teoría de grafos , un clique ( / k l i k / o / k l ɪ k / ) es un subconjunto de vértices de un grafo no dirigido de tal manera que cada dos vértices distintos en la camarilla son adyacentes; es decir, su subgrafo inducido está completo . Las camarillas son uno de los conceptos básicos de la teoría de gráficos y se utilizan en muchos otros problemas matemáticos y construcciones en gráficos. También se han estudiado camarillas 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 subgrafías completas se remonta al menos a la reformulación teórica de grafos de la teoría de Ramsey por Erdős & Szekeres (1935) , [1] el término camarilla proviene de Luce & Perry (1949) , quien utilizó subgrafías completas en redes sociales para modelos de 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 bioinformática .
Definiciones [ editar ]
Una camarilla , C , en un gráfico 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 es 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 extender al incluir 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 completar subgrafías que no son máximas.
Una camarilla máxima de un gráfico, G , es una camarilla, de modo que no hay una camarilla con más vértices. Por otra parte, el número clique ω ( 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 juntos cubren todos los bordes de G .
El número de cubierta de camarilla 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 de la gráfica.
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 del complemento . El problema de la cobertura de la camarilla se refiere a 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 bicliques necesarios para cubrir todos los bordes del gráfico.
Matemáticas [ editar ]
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 una gráfica tiene suficientes bordes, debe contener una camarilla grande. Por ejemplo, cada gráfico con vértices y más de los bordes deben contener una camarilla de tres vértices.
- El teorema de Ramsey establece que cada gráfica o su gráfica complementaria contiene una camarilla con al menos un número logarítmico de vértices. [4]
- Según un resultado de Moon & Moser (1965) , un gráfico con 3 n vértices puede tener como máximo 3 n camarillas máximas. Las gráficas que cumplen este límite son las gráficas de Luna-Moser K 3,3, ... , un caso especial de las gráficas de Turán que surgen como los casos extremos en el teorema de Turán.
- La conjetura de Hadwiger , aún no probada, 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 comprobada que relaciona el color de los gráficos con las camarillas.
Varias clases importantes de gráficos pueden definirse o caracterizarse por sus camarillas:
- Un gráfico de clúster es un gráfico cuyos componentes conectados son camarillas.
- Un gráfico de bloque es un gráfico cuyos componentes biconéctados son camarillas.
- Un gráfico cordal es un gráfico cuyos vértices se pueden ordenar en un orden de eliminación perfecto, un orden tal que los vecinos de cada vértice v que vienen después de v en el orden forman una camarilla.
- Una cografía es una gráfica cuyas subgrafías inducidas tienen la propiedad de que cualquier camarilla máxima se cruza con cualquier conjunto independiente máximo 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 disjuntas de bordes 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 camarilla es igual al número cromático en cada subgrafía inducida .
- Un gráfico dividido es un gráfico en el que una camarilla contiene al menos un punto final de cada borde.
- Un gráfico sin triángulo es un gráfico que no tiene camarillas aparte de sus vértices y bordes.
Además, muchas otras construcciones matemáticas involucran camarillas en los gráficos. Entre ellos,
- El complejo de camarilla de un gráfico G es un complejo simplicial abstracto X ( G ) con un simplex para cada camarilla en G
- 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 en un solo vértice. Es un ejemplo de gráfica mediana , y está asociada con un álgebra mediana en 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 camarillas es un método para combinar dos gráficos fusionándolos a lo largo de una camarilla compartida.
- El ancho de la camarilla 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 camarilla de un gráfico es el gráfico de intersección de sus camarillas máximas.
Los conceptos estrechamente relacionados con los subgrafos completos son subdivisiones de gráficos completos y gráficos menores completos . En particular, el teorema de Kuratowski y del teorema de Wagner caracterizan planar gráficos por prohibidos completos y completos bipartitos subdivisiones y menores, respectivamente.
Informática [ editar ]
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-complete , uno de los 21 problemas de Karp NP-complete . [6] También es intratable de parámetros fijos y difícil de aproximar . Sin embargo, se han desarrollado muchos algoritmos para calcular camarillas, que se ejecutan en tiempo exponencial (como el algoritmo Bron-Kerbosch ) o se especializan para graficar familias como gráficos planos o gráficos perfectos para los que se puede resolver el problema.tiempo polinómico .
Aplicaciones [ editar ]
La palabra "camarilla", en su uso teórico de grafos, surgió del trabajo de Luce & Perry (1949) , quien utilizó subgrafías completas 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 que utilizaba términos menos técnicos. Ambos trabajos tratan de descubrir camarillas en una red social utilizando matrices. Para los esfuerzos continuos para modelar gráficamente las camarillas sociales, véase, por ejemplo, Alba (1973) , Peay (1974) y Doreian & 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 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) discuten un problema similar de biclustering para los datos de expresión en el que los grupos deben ser 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 las características de la especie, donde dos vértices comparten un borde si existe una filogenia perfecta que combine esos dos caracteres. Samudrala y Moult (1998) modelan la predicción de la estructura de la proteína como un problema para 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. Análisis gráfico 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) usa camarillas para analizar redes de comunicaciones, y Paull y Unger (1959) las usan para diseñar circuitos eficientes para computar funciones booleanas parcialmente especificadas. Las camarillas también se han utilizado en la generación automática de patrones de prueba : una gran camarilla 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) usan camarillas para describir productos químicos en una base de datos químicos que tienen un alto grado de similitud con una estructura objetivo. Kuhl, Crippen y Friesen (1983) usan camarillas para modelar las posiciones en las que dos productos químicos se unirán entre sí.
No hay comentarios:
Publicar un comentario