Número de intersección (teoría de grafos)
En el campo matemático de la teoría de grafos , el número de intersección de un gráfico G = ( V , E ) es el número más pequeño de elementos en una representación de G como un gráfico de intersección de conjuntos finitos . De manera equivalente, es el número más pequeño de camarillas necesarias para cubrir todos los bordes de G . [1] [2]
Sea F una familia de conjuntos (permitiendo que se repitan los conjuntos en F ); entonces el gráfico de intersección de F es un gráfico no dirigido que tiene un vértice para cada miembro de F y una arista entre cada dos miembros que tienen una intersección no vacía. Cada gráfico se puede representar como un gráfico de intersección de esta manera. [3] El número de intersección del grafo es el menor número k tal que existe una representación de este tipo para la cual la unión de F tiene k elementos. [1]El problema de encontrar una representación de intersección de un gráfico con un número dado de elementos se conoce como el problema de base del gráfico de intersección . [4]
Una definición alternativa del número de intersección de un grafo G es que es el número más pequeño de camarillas en G ( subgrafos completos de G ) que juntos cubren todos los bordes de G. [1] [5] Un conjunto de camarillas con esta propiedad se conoce como cobertura de borde de camarilla o cubierta de camarilla de borde y, por esta razón, el número de intersección también se denomina a veces número de cubierta de camarilla de borde . [6]
La igualdad del número de intersección y el número de cobertura de clique de borde es fácil de probar. En una dirección, supongamos que G es el grafo de intersección de una familia F de conjuntos cuya unión U tiene k elementos. Entonces, para cualquier elemento x de U , el subconjunto de vértices de G correspondiente a conjuntos que contienen x forma una camarilla: dos vértices cualesquiera de este subconjunto son adyacentes, porque sus conjuntos tienen una intersección no vacía que contiene x . Además, cada arista en Gestá contenido en una de estas camarillas, porque un borde corresponde a una intersección no vacía y una intersección no está vacía si contiene al menos un elemento de U . Por tanto, las aristas de G pueden estar cubiertas por k camarillas, una por elemento de U. En la otra dirección, si un grafo G puede ser cubierto por k cliques, entonces cada vértice de G puede ser representado por el conjunto de cliques que contienen ese vértice. [5]
Trivialmente, un grafo con m aristas tiene un número de intersección como máximo m , ya que cada arista forma una camarilla y estas camarillas juntas cubren todas las aristas. [7]
También es cierto que todo grafo con n vértices tiene número de intersección como máximo n 2/4 . Más fuertemente, los bordes de cada gráfico de n vértices se pueden dividir en como máximo n 2/4 camarillas, todos los cuales son bordes simples o triángulos. [2] [5] Esto generaliza el teorema de Mantel de que un gráfico sin triángulos tiene como máximo n 2/4 aristas, ya que en un gráfico sin triángulos la única cobertura óptima de aristas de camarilla tiene una camarilla por arista y, por lo tanto, el número de intersección es igual al número de aristas. [2]
