Gráfico de intersección

En teoría de grafos, un gráfico de intersección es un gráfico que representa el esquema de intersección de una familia de conjuntos . Cualquier gráfico se puede representar como un gráfico de intersección, pero algunas clases especiales importantes se pueden definir en términos de los tipos de conjuntos utilizados para la representación como conjuntos de intersección.

Para obtener una descripción general de la teoría de gráficos de intersección y clases especiales importantes de gráficos de intersección, consulte McKee y McMorris [1] .

Formal definición

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

S_{i},i=0,1,2,...

creando un vértice para cada conjunto y conectando dos vértices y una arista si los dos conjuntos correspondientes tienen una intersección no vacía, es decir $v_{i}$ $Si}$ $v_{i}$ $v_{j}$

E(G)=\{\{v_{i},v_{j}\}|S_{i}\cap S_{j}\neq \emptyset \}

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

Cualquier grafo no dirigido G se puede representar como un grafo de intersección: para cualquier vértice del grafo G , formamos un conjunto que consta de aristas incidentes con . Dos de estos conjuntos tienen una intersección no vacía si y solo si los vértices correspondientes pertenecen a la misma arista. Erdős, Goodman y Poza [2] mostraron una construcción más eficiente (que requiere menos elementos en todos los conjuntos ) en la que el número total de elementos en los conjuntos no supera a , donde n es el número de vértices en el gráfico. Marchevsky [3] notó su afirmación de que todos los gráficos son gráficos de intersección , pero también recomendaron mirar el trabajo de Chulik [4] . El recuento de intersecciones de un gráfico es el número mínimo de elementos en las representaciones de un gráfico como un gráfico de intersección. $v_{i}$ $Si}$ $v_{i}$ $Si}$ $n^{2}/4$

Clases de gráficos de intersección

Muchas familias importantes de gráficos se pueden describir como gráficos de intersección de tipos de conjuntos limitados, como conjuntos derivados de ciertas configuraciones geométricas:

Un gráfico de intervalos se define como un gráfico de intersecciones de intervalos en una línea, o subgráficos de rutas conectadas .
Un gráfico de arco circular se define como un gráfico de intersección de arco circular .
La gráfica de polígonos en un círculo se define como la gráfica de intersecciones de polígonos con vértices que se encuentran en el círculo.
Una de las características de los grafos cordales es que son grafos de intersección de subgrafos conexos de un árbol .
Un gráfico trapezoidal se define como el gráfico de intersecciones de trapecios formados por dos líneas paralelas. Son una generalización de la noción de gráfico de permutación , que a su vez son un caso especial de la familia de complementos de gráficos de comparabilidad , conocidos como gráficos de comparabilidad.
El gráfico de círculo unitario se define como el gráfico de intersección de los círculos unitarios en el plano.
El teorema de empaquetamiento circular establece que los gráficos planos son exactamente los gráficos de intersección de familias de discos cerrados disjuntos (que se permiten tocar) en el plano.
La conjetura de Scheinerman (ahora un teorema) establece que cualquier gráfico plano puede representarse como un gráfico de intersecciones de segmentos de línea en un plano. Sin embargo, los gráficos de intersecciones de segmentos en una línea pueden ser no planos, y el reconocimiento de gráficos de intersecciones de segmentos en una línea es completo para la teoría de la existencia de números reales [5] .
El gráfico lineal de un gráfico G se define como el gráfico de intersección de las aristas de un gráfico G , donde cada arista se considera como un conjunto de dos de sus vértices finales.
Un gráfico de cuerdas es un gráfico de intersecciones de curvas en un plano .
Un gráfico tiene marco k si es un gráfico de intersección de rectángulos multidimensionales de dimensión k , pero no de dimensiones más pequeñas.

Variaciones y generalizaciones

Los análogos teóricos del orden de los gráficos de intersección son los órdenes de anidamiento . De la misma manera que la representación gráfica de intersección etiqueta cada vértice por el conjunto de aristas incidentes a él que tienen una intersección no vacía, la representación de orden de anidamiento f de un conjunto parcialmente ordenado etiqueta cada elemento con un conjunto tal que para cualquier x y y en ella si y sólo si . $x\leq y$ $f(x)\subsegmentoq f(y)$
recubrimiento nervioso

Literatura

K. Culik. Teoría de Grafos y sus Aplicaciones (Proc. Sympos. Smolenice, 1963). — Praga: Publ. Casa Checoslovaca Acad. Sci., 1964, págs. 13-20.
Paul Erdös, A. W. Goodman, Louis Posa. La representación de un gráfico por intersecciones de conjuntos // Canadian Journal of Mathematics. - 1966. - T. 18 . - S. 106-112 . -doi : 10.4153 / CJM-1966-014-3 .
Martín Charles Golumbic. Teoría de grafos algorítmicos y grafos perfectos. - Prensa académica, 1980. - ISBN 0-12-289260-7 .
Temas de Teoría de Grafos de Intersección. - Philadelphia: Society for Industrial and Applied Mathematics, 1999. - Vol. 2. - (Monografías SIAM sobre Matemáticas Discretas y Aplicaciones). — ISBN 0-89871-430-3 .
E. Szpilrain-Marczewski. Sur deux propriétés des classes d'ensembles // Fund. Matemáticas. . - 1945. - T. 33 . - S. 303-307 .
Marcus Schaefer. Graph Drawing, 17º Simposio Internacional, GS 2009, Chicago, IL, EE. UU., septiembre de 2009, artículos revisados . - Springer-Verlag, 2010. - vol. 5849. - S. 334-344. — (Apuntes de clase en informática). — ISBN 978-3-642-11804-3 . -doi : 10.1007 / 978-3-642-11805-0_32 .

Enlaces

Jan Kratochvíl, Una conferencia en video sobre gráficos de intersección (junio de 2007) Archivado el 17 de febrero de 2020 en Wayback Machine .
E. Prisner, A Journey through Intersection Graph County Archivado el 24 de abril de 2021 en Wayback Machine .