Gráfica de intersección

Gráfico que representa intersecciones entre conjuntos dados

Un ejemplo de cómo los conjuntos que se intersectan definen un gráfico.

En teoría de grafos , un grafo de intersección es un grafo que representa el patrón de intersecciones de una familia de conjuntos . Cualquier grafo puede representarse como un grafo de intersección, pero algunas clases especiales importantes de grafos pueden definirse por los tipos de conjuntos que se utilizan para formar una representación de intersección de ellos.

Definición formal

Formalmente, un gráfico de intersección G es un gráfico no dirigido formado a partir de una familia de conjuntos

${\displaystyle S_{i},\,\,\,i=0,1,2,\dots }$

creando un vértice v _i para cada conjunto S _i , y conectando dos vértices v _i y v _j mediante una arista siempre que los dos conjuntos correspondientes tengan una intersección no vacía , es decir,

${\displaystyle E(G)=\{\{v_{i},v_{j}\}\mid i\neq j,S_{i}\cap S_{j}\neq \emptyset \}.}$

Todos los gráficos son gráficos de intersección.

Cualquier grafo no dirigido G puede representarse como un grafo de intersección. Para cada vértice v _i de G , se forma un conjunto S _i que consiste en las aristas incidentes a v _i ; entonces dos de estos conjuntos tienen una intersección no vacía si y solo si los vértices correspondientes comparten una arista. Por lo tanto, G es el grafo de intersección de los conjuntos S _i .

Erdős, Goodman y Pósa (1966) ofrecen una construcción que es más eficiente, en el sentido de que requiere un número total menor de elementos en todos los conjuntos S _i combinados. Para ello, el número total de elementos del conjunto es como máximo ⁠número ²/4⁠ , donde n es el número de vértices del grafo. Atribuyen la observación de que todos los grafos son grafos de intersección a Szpilrajn-Marczewski (1945), pero dicen que hay que ver también a Čulík (1964). El número de intersección de un grafo es el número total mínimo de elementos en cualquier representación de intersección del grafo.

Clases de gráficos de intersección

Muchas familias de gráficos importantes pueden describirse como gráficos de intersección de tipos más restringidos de familias de conjuntos, por ejemplo, conjuntos derivados de algún tipo de configuración geométrica:

• Un gráfico de intervalo se define como el gráfico de intersección de intervalos en la línea real, o de subgráficos conectados de un gráfico de trayectoria .
• Un gráfico de indiferencia puede definirse como el gráfico de intersección de intervalos unitarios en la línea real.
• Un gráfico de arco circular se define como el gráfico de intersección de arcos en un círculo .
• Un gráfico de polígono-círculo se define como la intersección de polígonos con vértices en un círculo.
• Una caracterización de un gráfico cordal es como el gráfico de intersección de subgrafos conectados de un árbol .
• Un grafo trapezoidal se define como el grafo de intersección de trapecios formados a partir de dos líneas paralelas. Son una generalización de la noción de grafo de permutación , a su vez son un caso especial de la familia de los complementos de grafos de comparabilidad conocidos como grafos de cocomparabilidad.
• Un gráfico de disco unitario se define como el gráfico de intersección de discos unitarios en el plano.
• Un gráfico circular es el gráfico de intersección de un conjunto de cuerdas de un círculo.
• El teorema de empaquetamiento circular establece que los gráficos planares son exactamente los gráficos de intersección de familias de discos cerrados en el plano delimitados por círculos que no se cruzan.
• La conjetura de Scheinerman (ahora un teorema) establece que todo grafo plano también puede representarse como un grafo de intersección de segmentos de línea en el plano. Sin embargo, los grafos de intersección de segmentos de línea también pueden ser no planos, y el reconocimiento de grafos de intersección de segmentos de línea es completo para la teoría existencial de los números reales (Schaefer 2010).
• El gráfico lineal de un grafo G se define como el gráfico de intersección de las aristas de G , donde representamos cada arista como el conjunto de sus dos puntos finales.
• Un gráfico de cuerdas es el gráfico de intersección de curvas en un plano .
• Un gráfico tiene boxicidad k si es el gráfico de intersección de cajas multidimensionales de dimensión k , pero no de ninguna dimensión menor.
• Un gráfico de camarillas es el gráfico de intersección de camarillas máximas de otro gráfico.
• Un gráfico de bloques de un árbol de camarillas es el gráfico de intersección de componentes biconectados de otro gráfico.

Scheinerman (1985) caracterizó las clases de intersección de grafos , familias de grafos finitos que pueden describirse como los grafos de intersección de conjuntos extraídos de una familia de conjuntos dada. Es necesario y suficiente que la familia tenga las siguientes propiedades:

• Cada subgrafo inducido de un grafo en la familia también debe estar en la familia.
• Todo gráfico formado a partir de un gráfico de la familia mediante la sustitución de un vértice por una camarilla también debe pertenecer a la familia.
• Existe una secuencia infinita de grafos en la familia, cada uno de los cuales es un subgrafo inducido del siguiente grafo en la secuencia, con la propiedad de que cada grafo en la familia es un subgrafo inducido de un grafo en la secuencia.

Si las representaciones del gráfico de intersección tienen el requisito adicional de que los diferentes vértices deben estar representados por diferentes conjuntos, entonces se puede omitir la propiedad de expansión de camarilla.

Conceptos relacionados

Un análogo de la teoría del orden de los grafos de intersección son los órdenes de inclusión . De la misma manera que una representación de intersección de un grafo etiqueta cada vértice con un conjunto de modo que los vértices sean adyacentes si y solo si sus conjuntos tienen una intersección no vacía, una representación de inclusión f de un conjunto parcial etiqueta cada elemento con un conjunto de modo que para cualquier x e y en el conjunto parcial, x  ≤  y si y solo si f ( x ) ⊆  f ( y ).

Véase también

• Gráfico de contacto

Referencias

• Čulík, K. (1964), "Aplicaciones de la teoría de grafos a la lógica matemática y la lingüística", Teoría de grafos y sus aplicaciones (Proc. Sympos. Smolenice, 1963) , Praga: Publ. House Czechoslovak Acad. Sci., págs. 13-20, MR  0176940.
• Erdős, Paul ; Goodman, AW; Pósa, Louis (1966), "La representación de un gráfico por intersecciones de conjuntos" (PDF) , Revista Canadiense de Matemáticas , 18 (1): 106–112, doi :10.4153/CJM-1966-014-3, MR  0186575, S2CID  646660.
• Golumbic, Martin Charles (1980), Teoría de grafos algorítmicos y grafos perfectos , Academic Press, ISBN 0-12-289260-7.
• McKee, Terry A.; McMorris, FR (1999), Temas de teoría de grafos de intersección , Monografías SIAM sobre matemáticas discretas y aplicaciones, vol. 2, Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas, ISBN 0-89871-430-3, Sr.  1672910.
• Szpilrajn-Marczewski, E. (1945), "Sur deux propriétés desclasses d'ensembles", Fondo. Matemáticas. , 33 : 303–307, doi : 10.4064/fm-33-1-303-307 , SEÑOR  0015448.
• Schaefer, Marcus (2010), "Complejidad de algunos problemas geométricos y topológicos" (PDF) , Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, EE. UU., septiembre de 2009, Documentos revisados ​​, Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, págs. 334–344, doi : 10.1007/978-3-642-11805-0_32 , ISBN 978-3-642-11804-3.
• Scheinerman, Edward R. (1985), "Caracterización de clases de intersección de grafos", Discrete Mathematics , 55 (2): 185–193, doi :10.1016/0012-365X(85)90047-0, MR  0798535.

Lectura adicional

• Para una descripción general de la teoría de gráficos de intersección y de clases especiales importantes de gráficos de intersección, consulte McKee y McMorris (1999).

Enlaces externos

• Jan Kratochvíl, Videoconferencia sobre gráficos de intersección (junio de 2007)
• E. Prisner, Un viaje a través del condado de Intersection Graph