Gráfico de intersección

Gráfico que representa intersecciones entre conjuntos dados

Un ejemplo de cómo los conjuntos que se cruzan definen una gráfica.

En teoría de grafos , un gráfico de intersección es un gráfico que representa el patrón de intersecciones de una familia de conjuntos . Cualquier gráfico se puede representar como un gráfico de intersección, pero algunas clases especiales importantes de gráficos se pueden definir mediante los tipos de conjuntos que se utilizan para formar una representación de intersección de ellos.

Definicion 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 _vi para cada conjunto Si 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 gráfico no dirigido G puede representarse como un gráfico de intersección. Para cada vértice vi _de G , forme un conjunto Si _que consta de las aristas incidentes a vi _; entonces dos de estos conjuntos tienen una intersección no vacía si y sólo si los vértices correspondientes comparten una arista. Por tanto, G es la gráfica de intersección de los conjuntos Si _.

Erdős, Goodman y Pósa (1966) proporcionan 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 Si _combinados . Para ello, el número total de elementos del conjunto es como máximo ⁠norte ²/4⁠ , donde n es el número de vértices del gráfico. Acreditan la observación de que todos los gráficos son gráficos de intersección a Szpilrajn-Marczewski (1945), pero dicen que se debe ver también a Čulík (1964). El número de intersección de un gráfico es el número total mínimo de elementos en cualquier representación de intersección del gráfico.

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 intervalos se define como el gráfico de intersección de intervalos en la recta real, o de subgrafos conectados de un gráfico de trayectoria .
• Un gráfico de indiferencia se puede definir como el gráfico de intersección de intervalos unitarios en la recta real.
• Una gráfica de arco circular se define como la gráfica 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 esquinas 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 gráfico trapezoidal se define como el gráfico de intersección de trapecios formados por dos líneas paralelas. Son una generalización de la noción de gráfico de permutación , a su vez son un caso especial de la familia de los complementos de gráficos de comparabilidad conocidos como gráficos de cocomparabilidad.
• Un gráfico de discos unitarios se define como el gráfico de intersección de discos unitarios en el plano.
• Una gráfica circular es la gráfica de intersección de un conjunto de cuerdas de un círculo.
• El teorema de empaquetamiento de círculos establece que los gráficos planos son exactamente los gráficos de intersección de familias de discos cerrados en el plano delimitado por círculos que no se cruzan.
• La conjetura de Scheinerman (ahora un teorema) establece que cada gráfico plano también se puede representar como un gráfico de intersección de segmentos de línea en el plano. Sin embargo, las gráficas de intersección de segmentos de línea también pueden ser no planas, y reconocer las gráficas de intersección de segmentos de línea es completa para la teoría existencial de los reales (Schaefer 2010).
• La gráfica lineal de una gráfica G se define como la gráfica de intersección de las aristas de G , donde representamos cada arista como el conjunto de sus dos puntos finales.
• Una gráfica de cuerdas es la gráfica 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 árbol clique es el gráfico de intersección de componentes biconectados de otro gráfico.

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

• Cada subgrafo inducido de un grafo de la familia también debe estar en la familia.
• Todo grafo formado a partir de un grafo de la familia reemplazando un vértice por una camarilla también debe pertenecer a la familia.
• Existe una secuencia infinita de gráficos en la familia, cada uno de los cuales es un subgrafo inducido del siguiente gráfico de la secuencia, con la propiedad de que cada gráfico de la familia es un subgrafo inducido de un gráfico de 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 teórico del orden a los gráficos de intersección son los órdenes de inclusión . De la misma manera que una representación de intersección de un gráfico etiqueta cada vértice con un conjunto de modo que los vértices sean adyacentes si y sólo si sus conjuntos tienen una intersección no vacía, una representación de inclusión f de un poset etiqueta cada elemento con un conjunto de modo que para cualquier x e y en el poset, x  ≤  y si y solo si f ( x ) ⊆  f ( y ).

Ver 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 los grafos y sus aplicaciones (Proc. Sympos. Smolenice, 1963) , Praga: Publ. Casa Acad Checoslovaca. Sci., págs. 13-20, SEÑOR  0176940.
• Erdős, Paul ; Goodman, AW; Pósa, Louis (1966), "La representación de un gráfico mediante intersecciones establecidas" (PDF) , Canadian Journal of Mathematics , 18 (1): 106–112, doi :10.4153/CJM-1966-014-3, SEÑOR  0186575, S2CID  646660.
• Golumbic, Martin Charles (1980), Teoría algorítmica de grafos y gráficos 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 de SIAM sobre aplicaciones y matemáticas discretas, vol. 2, Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas, ISBN 0-89871-430-3, señor  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, 17º Simposio Internacional, GS 2009, Chicago, IL, EE. UU., septiembre de 2009, artículos 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 gráficos de intersección", Matemáticas discretas , 55 (2): 185–193, doi :10.1016/0012-365X(85)90047-0, SEÑOR  0798535.

Otras lecturas

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

enlaces externos

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