En teoría de grafos, dada una familia de conjuntos {Si}, se define su grafo de intersección como el grafo obtenido al representar cada conjunto Si 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.
Familia de 5 conjuntos y grafo de intersección asociado.
Cualquier grafo G puede ser representado como grafo de intersección: para cada vértice vi de G, construiremos un conjunto Si formado por todas las aristas incidentes en vi; 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), ISBN0-89871-430-3, MR 1672910.
Enlaces externos
E. Prisner, A Journey through Intersection Graph County
Datos:Q3498041
Marcha 01, 2023
grafo, intersección, teoría, grafos, dada, familia, conjuntos, define, grafo, intersección, como, grafo, obtenido, representar, cada, conjunto, vértice, modo, vértices, sean, adyacentes, solo, conjuntos, representan, tienen, intersección, vacía, familia, conju. En teoria de grafos dada una familia de conjuntos Si se define su grafo de interseccion como el grafo obtenido al representar cada conjunto Si por un vertice de modo que dos vertices sean adyacentes si y solo si los conjuntos que representan tienen interseccion no vacia Familia de 5 conjuntos y grafo de interseccion asociado Cualquier grafo G puede ser representado como grafo de interseccion para cada vertice vi de G construiremos un conjunto Si formado por todas las aristas incidentes en vi dos de estos conjuntos tendran interseccion no vacia si y solo si los vertices 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 interseccion de intervalos de la recta real Grafo arco circular grafo de interseccion de arcos definidos sobre una misma circunferencia Grafo cordal una de sus caracterizaciones es la de ser grafo de interseccion de subgrafos conexos de un arbol Bibliografia EditarMcKee 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 EditarE Prisner A Journey through Intersection Graph County Datos Q3498041 Obtenido de https es wikipedia org w index php title Grafo de interseccion amp oldid 120194468, wikipedia, wiki, leyendo, leer, libro, biblioteca,
