Schnittgraph ⇐ Proyectos de artículos

[adm2]

En teoría de grafos, un '''gráfico de intersección''' es un gráfico (teoría de grafos) que representa los cortes (intersección) de una familia de conjuntos (matemáticas) como aristas. Cada conjunto corresponde a un nodo en el gráfico de intersección. Por cada par de dos conjuntos de la familia que se cruzan, el gráfico de intersección tiene una arista; a la inversa, no hay ninguna arista entre dos conjuntos que no se cruzan.

== Definición formal ==
Formalmente, un gráfico de intersección G es un gráfico no dirigido (teoría de grafos) de la familia de conjuntos

: S_i, \,\,\, i = 0, 1, 2, \dots

representa representando cada conjunto S_i mediante un nodo v_i, y dos nodos v_i y v_j están conectados exactamente entonces, si los conjuntos que representan forman un conjunto vacío|corte no vacío, es decir

: E(G) = \{ \{ v_i, v_j \} \mid i \neq j, S_i \cap S_j \neq \empty \}.

== Literatura ==

*
== Lectura adicional ==

* Puede encontrarse una descripción general de la teoría de los gráficos de intersección en McKee y McMorris (1999).

McKee, Terry A.; McMorris, F. R. (1999), Temas de teoría de grafos interseccionales, 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, MR 1672910.

== Enlaces externos ==

* Jan Kratochvíl, [https://videolectures.net/sicgt07_kratochvil_gig/ Una videoconferencia sobre gráficos de intersección (junio de 2007)]
* E. Prisner, [http://www.eprisner.de/Journey/Rahmen.html Un viaje por el condado de Intersection Graph]
Categoría: Teoría de grafos

More details: https://de.wikipedia.org/wiki/Schnittgraph