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.
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.
YouTube Encyclopedic
-
1/3Views:132 1293 9851 726
-
Matemáticas Discretas - Teoría de Grafos (Parte 1/2)
-
9. Grafos- grado entrada, camino... Examen UNED
-
Cálculo - Intersección de una Gráfica - Video 2 - Intersection of a Graph - GCMatematica
Transcription
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
| Control de autoridades |
|
|---|
Datos: Q3498041
Esta página se editó por última vez el 11 oct 2019 a las 12:42.