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 menor número de camarillas necesarios para cubrir todos los bordes de G . [1] [2]
Gráficos de intersección
Sea F una familia de conjuntos (que permite que los conjuntos de F se repitan); entonces la gráfica de intersección de F es una gráfica no dirigida que tiene un vértice para cada miembro de F y un borde 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 de la gráfica 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]
Cubiertas de borde Clique
Una definición alternativa del número intersección de una gráfica G es que es el número más pequeño de camarillas en G ( completos subgraphs de G ) que juntos cubren todos los bordes de G . [1] [5] Un conjunto de camarillas con esta propiedad se conoce como cubierta 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 la camarilla de borde es fácil de demostrar. En una dirección, suponga que G es la gráfica 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 borde en G está contenido en una de estas camarillas, porque un borde corresponde a una intersección no vacía y una intersección es no vacía si contiene al menos un elemento de U . Por lo tanto, los bordes de G pueden ser cubiertos por k camarillas, uno por cada elemento de U . En la otra dirección, si un gráfico G puede estar cubierto por k camarillas, entonces cada vértice de G puede estar representado por el conjunto de camarillas que contienen ese vértice. [5]
Límites superiores
Trivialmente, un gráfico con m bordes tiene un número de intersección como máximo m , ya que cada borde forma una camarilla y estas camarillas juntas cubren todos los bordes. [7]
También es cierto que cada gráfico con n vértices tiene número de intersección a lo sumo n 2 /4 . Más fuertemente, los bordes de cada n gráfico -vertex pueden dividirse en un máximo de n 2 /4 camarillas, todos los cuales son o bien bordes individuales o triángulos. [2] [5] Este generaliza el teorema de Mantel que un gráfico libre de triángulo tiene como máximo n 2 /4 bordes, para en un gráfico libre de triángulo de la cubierta solamente óptima borde camarilla tiene uno clique por borde y por lo tanto el número de intersección es igual a la número de aristas. [2]
Una cota aún más fuerte es posible cuando el número de bordes es estrictamente mayor que n 2 /4 . Sea p el número de pares de vértices que no están conectados por una arista en el gráfico G dado , y sea t el único entero para el cual ( t - 1) t ≤ p < t ( t + 1) . Entonces el número de intersección de G es como máximo p + t . [2] [8]
Los gráficos que son el complemento de un gráfico disperso tienen números de intersección pequeños: el número de intersección de cualquier gráfico de n- vértice G es como máximo 2 e 2 ( d + 1) 2 ln n , donde e es la base del logaritmo natural y d es el máximo grado de la gráfica complemento de G . [9]
Complejidad computacional
Probar si una gráfica dada G tiene un número de intersección como máximo con un número dado k es NP-completo . [4] [10] [11] Por lo tanto, también es NP-difícil calcular el número de intersección de un gráfico dado.
Sin embargo, el problema de calcular el número de intersección es tratable con parámetros fijos : es decir, hay una función f tal que, cuando el número de intersección es k , el tiempo para calcularlo es como máximo el producto de f ( k ) y un polinomio en n . Esto puede demostrarse observando que hay como máximo 2 k vecindarios cerrados distintos en el gráfico (dos vértices que pertenecen al mismo conjunto de cliques tienen el mismo vecindario) y que el gráfico formado al seleccionar un vértice por vecindario cerrado tiene el mismo número de intersección como el gráfico original. Por lo tanto, en tiempo polinomial, la entrada se puede reducir a un núcleo más pequeño con un máximo de 2 k vértices; la aplicación de un procedimiento de búsqueda de retroceso en el tiempo exponencial a este núcleo conduce a una función f que es doble exponencial en k . [12] La dependencia doble exponencial de k no se puede reducir a exponencial simple mediante una kernelización del tamaño del polinomio, a menos que la jerarquía del polinomio colapse, [13] y si la hipótesis del tiempo exponencial es cierta, entonces la dependencia doble exponencial es necesaria independientemente de si se utiliza la kernelización. [14]
También se conocen algoritmos más eficientes para ciertas clases especiales de gráficos. El número de intersección de un gráfico de intervalo siempre es igual a su número de camarillas máximas , que se puede calcular en tiempo polinomial. [15] [16] De manera más general, en los gráficos cordales , el número de intersección puede calcularse mediante un algoritmo que considera los vértices en un orden de eliminación del gráfico y que, para cada vértice v , forma una camarilla para v y sus vecinos posteriores. siempre que al menos uno de los bordes incidentes con v no esté cubierto por ninguna camarilla anterior. [dieciséis]
Ver también
- Dimensión bipartita , la menor cantidad de bicliques necesarios para cubrir todos los bordes de un gráfico
- Clique cover , el problema NP-difícil de encontrar un pequeño número de cliques que cubran todos los vértices de un gráfico
Referencias
- ^ a b c Bruto, Jonathan L .; Yellen, Jay (2006), Teoría de grafos y sus aplicaciones , CRC Press, p. 440, ISBN 978-1-58488-505-4.
- ^ a b c d Roberts, Fred S. (1985), "Applications of edge coverings by cliques", Discrete Applied Mathematics , 10 (1): 93-109, doi : 10.1016 / 0166-218X (85) 90061-7 , MR 0770871.
- ^ Szpilrajn-Marczewski , E. (1945), "Sur deux propriétés des classes d'ensembles", Fondo. Matemáticas. , 33 : 303–307, doi : 10.4064 / fm-33-1-303-307 , MR 0015448.
- ^ a b Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , W. H. Freeman , ISBN 0-7167-1045-5, Problema GT59.
- ^ a b c Erdős, Paul ; Goodman, AW; Pósa, Louis (1966), "La representación de un gráfico por intersecciones de conjuntos" (PDF) , Canadian Journal of Mathematics , 18 (1): 106–112, CiteSeerX 10.1.1.210.6950 , doi : 10.4153 / CJM-1966- 014-3 , MR 0186575.
- ^ Michael, TS; Quint, Thomas (2006), "Sphericity, cubicity, and edge clique covers of graphs", Discrete Applied Mathematics , 154 (8): 1309-1313, doi : 10.1016 / j.dam.2006.01.004.
- ^ Balakrishnan, VK (1997), esquema de la teoría y problemas de la teoría de grafos de Schaum , McGraw-Hill Professional, p. 40, ISBN 978-0-07-005489-9.
- ^ Lovász, L. (1968), "Sobre el recubrimiento de gráficos", en Erdős, P .; Katona, G. (eds.), Actas del Coloquio celebrado en Tihany, Hungría, 1966 , Academic Press, págs. 231-236. Como lo cita Roberts (1985) .
- ^ Alon, Noga (1986), "Cubriendo gráficas por el número mínimo de relaciones de equivalencia" (PDF) , Combinatorica , 6 (3): 201-206, doi : 10.1007 / bf02579381.
- ^ Orlin, J. (1977), "El contentamiento en la teoría de grafos: cubriendo grafos con camarillas", Proc. Kon. Ned. Acad. Mojado. , Serie A, 80 (5): 406–424, doi : 10.1016 / 1385-7258 (77) 90055-5. Como lo cita Roberts (1985) .
- ^ Kou, LT; Stockmeyer, LJ ; Wong, CK (1978), "Cubriendo bordes por camarillas con respecto a conflictos de palabras clave y gráficos de intersección", Comunicaciones del ACM , 21 (2): 135-139, doi : 10.1145 / 359340.359346.
- ^ Gramm, Jens; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf (2009), "Reducción de datos y algoritmos exactos para la cobertura de la camarilla" (PDF) , Journal of Experimental Algorithmics , 13 (2): 2-15, doi : 10.1145 / 1412228.1412236.
- ^ Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus (2012), "Separación de portadas y gráficos de camarillas: Nuevos resultados de incompresibilidad", en Czumaj, Artur; Mehlhorn, Kurt ; Pitt, Andrew; et al. (eds.), Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012, Warwick, Reino Unido, 9-13 de julio de 2012, Actas, Parte I , Lecture Notes in Computer Science, 7391 , págs. 254-265, arXiv : 1111.0570 , doi : 10.1007 / 978-3-642-31594-7_22 , ISBN 978-3-642-31593-0.
- ^ Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał (2013), "Los algoritmos conocidos para EDGE CLIQUE COVER son probablemente óptimos", Proc. 24o Simposio ACM-SIAM sobre algoritmos discretos (SODA 2013) , 45 , págs. 67–83, arXiv : 1203.1754 , doi : 10.1137 / 130947076.
- ^ Opsut, RJ; Roberts, FS (1981), "Sobre el mantenimiento de la flota, la radiofrecuencia móvil, la asignación de tareas y los problemas de fase del tráfico", en Chartrand, G .; Alavi, Y .; Goldsmith, DL; Lesniak-Foster, L .; Lick, DR (eds.), The Theory and Applications of Graphs , Nueva York: Wiley, págs. 479–492. Como lo cita Roberts (1985) .
- ^ a b Scheinerman, Edward R .; Trenk, Ann N. (1999), "Sobre el número de intersección fraccional de un gráfico", Graphs and Combinatorics , 15 (3): 341–351, doi : 10.1007 / s003730050068.
enlaces externos
- Weisstein, Eric W. "Número de intersección" . MathWorld .