Grafo de intersección

Familia de 5 conjuntos y grafo de intersección asociado.

En teoría de grafos, dada una familia de conjuntos {S_i}, se define su grafo de intersección como el grafo obtenido al representar cada conjunto S_i por un vértice de modo que dos vértices sean adyacentes si y solo si los conjuntos que representan tienen intersección no vacía.

Cualquier grafo G puede ser representado como grafo de intersección: para cada vértice v_i de G, construiremos un conjunto S_i formado por todas las aristas incidentes en v_i; dos de estos conjuntos tendrán intersección no vacía si y solo si los vértices correspondientes a cada conjunto comparten una arista.

Al restringir las familias de conjuntos a ciertos tipos, se obtienen las siguientes familias de grafos:

• Grafo de intervalos, el grafo de intersección de intervalos de la recta real.
• Grafo arco circular, grafo de intersección de arcos definidos sobre una misma circunferencia.
• Grafo cordal, una de sus caracterizaciones es la de ser grafo de intersección de subgrafos conexos de un árbol.

Bibliografía

• McKee, Terry A.; McMorris, F. R. (1999), Topics in Intersection Graph Theory, Philadelphia: Society for Industrial and Applied Mathematics (SIAM Monographs on Discrete Mathematics and Applications, No. 2), ISBN 0-89871-430-3, MR 1672910 .

Enlaces externos

• E. Prisner, A Journey through Intersection Graph County

• Datos: Q3498041